 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/discrete-mathematics-continuous-mathematics-and-probability/2/d/solution

Use mathematical induction with the defining Fibonacci recurrence. Both identities hold at

n = 0

: their two sides are zero. If the first holds at

n

, then

\sum_{i = 0}^{n + 1} F_{i} = F_{n + 2} - 1 + F_{n + 1} = F_{n + 3} - 1.

If the second holds at

n

, then

\sum_{i = 0}^{n + 1} F_{i}^{2} = F_{n} F_{n + 1} + F_{n + 1}^{2} = F_{n + 1} (F_{n} + F_{n + 1}) = F_{n + 1} F_{n + 2} .

Each inductive hypothesis therefore advances to

n + 1

 New to topics? Read the docs here!