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

The base case is $F_5=5$, so $5\mid F_5$. To relate successive blocks of five, use the Fibonacci addition formula:This identity can also be obtained simply by applying the Fibonacci recurrence five times. If the mathematical induction hypothesis is $5\mid F_{5n}$, thenis a sum of two multiples of five. HenceThe generalisation is Fibonacci multiple-index divisibility: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$.