189-235A: Basic Algebra I Assignment 1

Due: Wednesday, September 15

Let S and T be the sets {a, b, c}and {x, y} respectively.

1. How many functions are there from S to T?

2. How many injective functions?

3. How many surjective functions?

Let X be a set, and let F(X) be the set of all functions from X to itself. This set is equipped with a natural binary operation (f, g) ↦ fg , given by the composition of functions.

4. Show that f(gh) = (fg)h for all f, g, h in F(X). (In other words, the operation of composition of funcions is associative.)

5. Show, by providing an example, that fg need not be equal to gf.

6. Prove that ∑_{k=0}^{n} (\frac{n}{k}) = 2^{n}, and that ∑_{k=0}^{n}(−1)^{k} (\frac{n}{k}) = 0, using the binomial theorem.

7. Using the Euclidean algorithm compute the gcd of 910091 and 3619. Show the steps in your calculation.

8. Using induction, show that

1^{2} + 2^{2} + 3^{2} + ⋯ + n^{2} = \frac{1}{3}n^{3} + \frac{1}{2}n^{2} + \frac{1}{6}n.

9. Using induction, show that the addition law in N is associative directly from the axioms defining addition in N.

10. Show that the expression

1^{k} + 2^{k} + 3^{k} + ⋯ + n^{k}

can be written as a polynomial in n of degree at most k + 1.