Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 2 / c / Solution

Fix $m\ge 1$ and use two-base mathematical induction on $n$. At $n=0$, the proposed right side is $F_m$; at $n=1$, it is $F_{m-1}+F_m=F_{m+1}$. Suppose the identity holds at $n$ and $n+1$. The defining recurrence relation for the Fibonacci numbers givesThis is the assertion at $n+2$, completing the proof of the Fibonacci addition formula. The argument includes $m=1$, since $F_{m-1}=F_0$ is defined.