# Induction Proof: Fibonacci Numbers Identity with Sum of Two Squares

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!

-
While this doesn't answer your question, you could probably try proving that $f_n=\frac{a^n-b^n}{\sqrt{5}}$ where $a=\frac{\sqrt{5}+1}{2}$ and $b=\frac{1-\sqrt{5}}{2}$ using induction and then proving your theorem. –  user60469 Feb 11 '13 at 16:36

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

-
I.e. it's just $\rm\: M^{2n} = (M^n)^2.\:$ It's the special equal-argument case of the Fibonacci addition formula, which has an analogous matrix proof. –  Math Gems Feb 11 '13 at 22:01
absolutely bizarre –  user58512 Feb 11 '13 at 22:06

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...).

-
One tiny note: cleanly expressing $f_{2n+3}$ in terms of $f_{2n+1}$ and $f_{2n-1}$ requires a little bit of a trick; I get $f_{2n+3} = f_{2n+2}+f_{2n+1} = 2f_{2n+1}+f_{2n}$ and here to eliminate the $f_{2n}$ term you need to use $f_{2n} = f_{2n+1}-f_{2n-1}$ which, while algebraically trivial, isn't necessarily immediately obvious. –  Steven Stadnicki Feb 11 '13 at 17:47

Use $f_{n} = f_{n-2} + f_{n-1}$ and $f_{n+1} = f_{n-1} + f_n$ to turn $f_n^2 + f_{n+1}^2$ into $$f_{n-2}^2 + 2 f_{n-2} f_{n-1} + 2 f_{n-1}^2 + 2 f_{n-1} f_n + f_n^2$$

Then if we have $f_{n-1}^2 + f_{n}^2 = f_{2n-1}$ and $f_{n-2}^2 + f_{n-1}^2 = f_{2n-3}$ by induction we can rewrite that to $$f_{2n-3} + 2 f_{n-2} f_{n-1} + 2 f_{n-1} f_n + f_{2n-1}$$

To show this is equal to $f_{2n+1}$ we would need some extra knowledge about what $f_{n-1} f_n$ is.

So induction doesn't look like a good way to prove this.

-
That's basically what I was getting. I don't understand why this practice problem is in the induction section of the book. Thanks for your help! –  Luke8ball Feb 11 '13 at 16:46

At first we get $$f_{n+1}^2+f_{n+2}^2 = f_n^2 +f_{n+1}^2+(f_{n+2}^2 -f_n^2)=f_{2n+1}+(f_{n+2}^2 -f_n^2)$$

If $f_{n+2}^2 -f_n^2=f_{2n+2}$, then proof is completed. So we will show that $$\begin{cases} f_n^2+f_{n+1}^2=f_{2n+1}\\ f_{n+2}^2-f_n^2=f_{2n+2} \end{cases}$$

for all $n$ by using the induction.

If $n=1$, it is trivial. If these formulas hold at $n=k$, then $$f_{k+1}^2+f_{k+2}^2 = f_k^2 +f_{k+1}^2+(f_{k+2}^2 -f_k^2)=f_{2k+1}+f_{2k+2}=f_{2(k+1)+1}$$ and $$\begin{array}{lcl} f_{k+3}^2 -f_{k+1}^2&=&(f_{k+2}+f_{k+1})^2-f_{k+1}^2\\ &=&(f_{k+2}^2+f_{k+1}^2)+2f_{k+2}f_{k+1}-f_{k+1}^2 \\ &=&f_{2k+3} + f_{k+1}(f_{k+2}+f_k) \\ &=& f_{2k+3}+(f_{k+2}-f_k)(f_{k+2}+f_k)\\ &=& f_{2k+3}+f_{2k+2}=f_{2(k+1)} \end{array}$$ So these formulas are also hold at $n=k+1$.

-