Proof of the addition formula for Fibonacci numbers by induction

Proof

We argue by induction on $m$, for two consecutive values of $m$ at a time and all $n$ at once.

1. Let $F_k$ be the Fibonacci numbers, with $F_0 = 0$, $F_1 = 1$ and $F_{k+2} = F_{k+1} + F_k$.
2. For a natural number $m$, let $E(m)$ be the claim that $F_{m+n+1} = F_m F_n + F_{m+1} F_{n+1}$ for every natural number $n$.
3. Let $P(m)$ be the claim that $E(m)$ and $E(m + 1)$ both hold.
4. $E(0)$ holds: for every $n$, $F_0 F_n + F_1 F_{n+1} = 0 + F_{n+1} = F_{n+1}$.
5. $E(1)$ holds: $F_2 = F_1 + F_0 = 1$, so for every $n$, $F_1 F_n + F_2 F_{n+1} = F_n + F_{n+1} = F_{n+2}$. Thus $P(0)$ holds.
6. Assume $P(m)$, and let $n$ be a natural number. By the recurrence, $F_{(m+2)+n+1} = F_{m+n+1} + F_{(m+1)+n+1}$.
7. By $E(m)$ and $E(m + 1)$, this is $\left(F_m F_n + F_{m+1} F_{n+1}\right) + \left(F_{m+1} F_n + F_{m+2} F_{n+1}\right)$.
8. Grouping terms, it equals $(F_m + F_{m+1}) F_n + (F_{m+1} + F_{m+2}) F_{n+1} = F_{m+2} F_n + F_{m+3} F_{n+1}$, by the recurrence.
9. So $E(m + 2)$ holds. Together with $E(m + 1)$, this gives $P(m + 1)$.
10. By induction, $P(m)$ holds for every natural number $m$. In particular $F_{m+n+1} = F_m F_n + F_{m+1} F_{n+1}$ for all natural numbers $m$ and $n$.