 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/discrete-mathematics-continuous-mathematics-and-probability-resit/2/c/ii/solution

Fix

n \geq 1

m

with two initial cases, as appropriate for the second-order Fibonacci recurrence. At

m = 0

, the right side is

F_{n - 1} F_{0} + F_{n} F_{1} = F_{n}

. At

m = 1

, it is

F_{n - 1} + F_{n} = F_{n + 1}

If the identity holds at

m

and

m + 1

, then

F_{n + m + 2} = F_{n + m + 1} + F_{n + m} = F_{n - 1} (F_{m + 1} + F_{m}) + F_{n} (F_{m + 2} + F_{m + 1}) = F_{n - 1} F_{m + 2} + F_{n} F_{m + 3} .

Hence the induction establishes

F_{n + m} = F_{n - 1} F_{m} + F_{n} F_{m + 1} (n \geq 1, m \geq 0) .

 New to topics? Read the docs here!