Recurrence relations/recursion & Induction

Recurrence relations and recursive definitions have a lot in common with induction - the value of a function at a higher value is defined in terms of its values at a smaller value.

Often a recursive construction will require an inductive proof of its correctness.

Example: $a_0 = 1$, $a_{n+1} = 2a_n + 1$, what is a closed form expression for $a_n$?

Then, show that the best solution to the $n-disk$ towers of Hanoi puzzle requires $2^n - 1$ steps.

A classic example of a recursive definition is that of the Fibonnaci numbers: they are defined as: $F_1 = F_2 = 1$ and, for $n \geq 1$, $F_{n+2} = F_{n+1} + F_n$.

11 Prove the following identity for Fibonacci numbers: for all $n \geq 1$:

$$F_1^2 + F_2^2 + \ldots + F_n^2 = F_n \cdot F_{n+1}$$

12 Prove that consecutive Fibonacci numbers are always relatively prime. (Hint: Try finite descent!)

13 For the Fibonacci numbers, show:

$$F_n = {n-1\choose 0} + {n-2\choose 1} + {n-3\choose 2} + \ldots$$

14 Show that every positive integer can be expressed uniquely as the sum of distinct, non-consecutive Fibonacci numbers (here, non-consecutive means that no two of the Fibonacci number in the sum are consecutive Fibonacci numbers).