Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
    

4 Answers 4

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

share|improve this answer
1  
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

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

share|improve this answer
    
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

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

share|improve this answer

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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.