Induction Proof: Fibonacci Numbers Identity with Sum of Two Squares

Solution 1:

Since fibonacci numbers are a linear recurrence - and the initial conditions are special - we can express them by a matrix $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$$ this is easy to prove by induction:

• $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^1 = \begin{pmatrix} F_{2} & F_1 \\ F_1 & F_{0} \end{pmatrix}$$
• $$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_n + F_{n+1} & F_{n+1} \\ F_n + F_{n-1} & F_{n} \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{pmatrix}$$

Now your theorem follows from $$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}^2 = \begin{pmatrix} F_{n+1}^2 + F_n^2 & - \\ - & - \end{pmatrix} = \begin{pmatrix} F_{2n+1} & F_{2n} \\ F_{2n} & F_{2n-1} \end{pmatrix}$$

https://en.wikipedia.org/wiki/Fibonacci_number

Solution 2:

Though the matrix proof by user58512 is much more elegant, it is also possible to prove this by straight-forward induction. What you need to prove is $$f_{2(n+1)+1} = f_{n+1}^2 + f_{n+2}^2$$ using only $f_{2k+1} = f_{k}^2 + f_{k+1}^2$ for $k\leq n$ and the usual recurrence relation for the Fibonacci numbers. On the left you use it two times, until you have only odd numbers left, namely $2n+1$ and $2n-1$, and plug in the formula you are trying to prove. Now apply the Fibonacci recurrence to both sides until you have only terms in $f_n$ and $f_{n-1}$ left. You'll see that the terms on both sides will cancel, and that's it. (As it looks a bit like homework to me, I've left out the details and just sketched the path...).