[Math] Induction Proof: Fibonacci Numbers Identity with Sum of Two Squares

fibonacci-numbersinduction

Using induction, how can I show the following identity about the fibonacci numbers? I'm having trouble with simplification when doing the induction step.

Identity: $$f_n^2 + f_{n+1}^2 = f_{2n+1}$$

I get to:

$$f_{n+1}^2 + f_{n+2}^2$$

Should I replace $f_{n+2}$ using the recursion? When I do that, I end up with the product of terms, and that just doesn't seem right. Any guidance on how to get manipulate during the induction step?

Thanks!

Best Answer

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

Related Question