1. Surjectivity

Let f:A→B. Prove that f is surjective if and only if, for all sets C and functions g,h:B→C, g∘f = h∘f implies g = h.

1.1. Solution

Suppose first that f is surjective. Fix C, g, and h and suppose that g≠h. Then there exists some x in B such that g(x)≠h(x). Because f is surjective, there is some y in A such that f(y) = x. But then (g∘f)(y) = g(f(y)) = g(x) ≠ h(x) = h(f(y)) = (h∘f)(y). It follows that g∘f ≠ h∘f. By contraposition we have that if f is surjective, then g∘f = h∘f implies g = h.

Alternatively, suppose that f is not surjective. Then there is some x in B such that f(y)≠x for all y in A. Let C = {0,1} and define the functions g(z) = 1 for all z in B and h(z) = 1 if z≠x, h(z) = 0 if z=x. Now for any y in A, we have (g∘f)(y) = g(f(y)) = 1 and (h∘f)(y) = h(f(y)) = 1 (because f(y) can't equal x). But g≠h because they disagree on x. So we have demonstrated that if f is not surjective, then it is not the case that for all C, g, h, g∘f = h∘f implies g = h.

2. A recursively-defined function

Let f:ℕ→ℤ be defined by the rule:

• f(0) = a
• f(1) = b

• For n > 1, f(n) = 2f(n-1) - f(n-2)

where a,b∈ℤ.

Show that there exist constants c and d (which may depend on a and b but not on n), such that f(n) = cn+d for all n∈ℕ.

2.1. Solution

First let's find c and d and then show (by induction) that they work.

Look at f(0) and f(1), we have

• c⋅0+d = a
• c⋅1+d = b

The first case gives us d = a; the second gives us b = c + d = c + a or c = b - a. So our formula for f is f(n) = (b-a)n + a. Now we'll show that this works.

Base case: f(0) = (b-a)⋅0 + a = a, f(1) = (b-a)⋅1 + a = b.

Induction step: Let n > 1, compute f(n) = 2f(n-1) - f(n-2) = 2((b-a)(n-1)+a) - ((b-a)(n-2)+a) = (b-a)(2(n-1)-(n-2)) + a(2-1) = (b-a)(2n-2+n+2) + a = (b-a)n + a. Note the second step uses the (strong) induction hypothesis that f(n') = (b-a)n' + a for all n' ≤ n-1.

3. Sums of products

Prove that the following identity holds for all n∈ℕ:

3.1. Solution

The proof is by induction on n. The base case is n=0; here the left-hand side is 1 + 0 (since the sum is empty), while the right-hand side is 1 (since the product is empty).

For n > 0, we have

Here step (2) uses the induction hypothesis.