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∈ℕ: