# 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.

# 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∈ℕ.

# 3. Sums of products

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