 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/3/b/solution

F_{5} = 5

, so

5 ∣ F_{5}

. To relate successive blocks of five, use the Fibonacci addition formula:

F_{k + 5} = F_{5} F_{k + 1} + F_{4} F_{k} = 5 F_{k + 1} + 3 F_{k} .

This identity can also be obtained simply by applying the Fibonacci recurrence five times. If the mathematical induction hypothesis is

5 ∣ F_{5 n}

, then

F_{5 (n + 1)} = 5 F_{5 n + 1} + 3 F_{5 n}

is a sum of two multiples of five. Hence

F_{5} ∣ F_{5 n} for every integer n > 0.

F_{m} ∣ F_{mn} (m, n \geq 1) .

Indeed,

F_{mn + m} = F_{m} F_{mn + 1} + F_{m - 1} F_{mn}

, so precisely the same mathematical induction works with

5

replaced by

m

 New to topics? Read the docs here!