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.

Possible Duplicate:
Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

Hi!

I needed to solve several Fibonaccii identites, but I couldn't come along with two of them. Could you please help me to prove them?

i) $F_{n-1}^2 + F_n^2 = F_{2n}$.

ii) $F_{n-1}F_n + F_n F_{n+1} = F_{2n+1}$.

I tried using induction but I got nothing useful then.

Thanks in advance!

share|improve this question
    
Have you tried using the explicit form for the fibonacci sequence? Using that, it shouldn't be to hard I think. –  gfes Jun 5 '11 at 21:58
2  
This is a special case of math.stackexchange.com/questions/11477/… –  Mike Spivey Jun 5 '11 at 21:58
    
@Mike-Spivey Is it really? There is no way of setting m that is equals my identity exactly. Do you have another hint for me? –  muffel Jun 5 '11 at 22:15
    
@gfes I did. But I got stuck on i) after getting $$F_{n+1}F_n + F_{n+2}F_{n+1} = $$$$\cdots= F_{n-1} F_{n+1} + F_n^2 + F_{n+1} F_n + F_{n-1} F_n + F_{n+1} F_n $$$$= F_{2n+1} + F_{n-1} F_{n+1} + F_n^2 + F_{n+1} F_n$$ –  muffel Jun 5 '11 at 22:17
    
Are you sure your identities are correct? According to Mathematica they aren't. Or maybe your indexing for the Fibonacci sequence is off by 1 from the standard way of doing it? That would account for the discrepancy between your identities and the one in linked question. –  Mike Spivey Jun 5 '11 at 22:34
add comment

marked as duplicate by Mike Spivey, Sivaram, Arturo Magidin, Ross Millikan, t.b. Jun 6 '11 at 9:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers

up vote 2 down vote accepted

In Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$ it was proved that $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$ if you substitute $n$ for $m$ you get $$ F_{2n} = F_{n-1}F_n + F_n F_{n+1}$$ ( which cannot be $F_{2n+1}$ too ) and if you substitute $n-1$ for $m$ you get $$ F_{2n-1} = F_{n-1}^2 + F_n^2$$ ( which cannot be $F_{2n}$ too ) But if you set $f_{n-1}=F_{n}$ you get the euations $$ f_{2n-1} = f_{n-2}f_{n-1} + f_{n-1} f_{n}$$ or, after incrementing n by $1$ $$ f_{2n+1} = f_{n-1}f_{n} + f_{n} f_{n+1}$$ also we get $$ f_{2n-2} = f_{n-2}^2 + f_{n-1}^2$$ and again incrementing $n$ by $1$ gives $$ f_{2n} = f_{n-1}^2 + f_{n}^2$$

share|improve this answer
    
thank you! That helped me a lot! –  muffel Jun 6 '11 at 6:18
add comment

Doing this in a comment is a bit cumbersome because of the lack of space, so I'll post it this way.

Let's first set some notation: $\phi_{\pm} = \frac{1\pm\sqrt{5}}{2}$, then we have $F_n = \frac{\phi_+^{n+1} - \phi_-^{n+1}}{\sqrt{5}}$ in your convention.

So then $F_{n-1}^2+F_n^2 = \frac{1}{5}\left((\phi_+^{n} - \phi_-^{n})^2 + (\phi_+^{n+1} - \phi_-^{n+1})^2\right) = \frac{1}{5}\left(\phi_+^{2n} + \phi_-^{2n} - 2(\phi_+\phi_-)^n + \phi_+^{2n+2} + \phi_-^{2n+2} - 2(\phi_+\phi_-)^{n+1}\right)$

Now $\phi_\pm^2 = 1+\phi_\pm$, and $\phi_+\phi_- = -1$, so this 'reduces' to:

$\frac{1}{5}\left(\phi_+^{2n} + \phi_-^{2n} - 2(-1)^n + \phi_+^{2n+2} + \phi_-^{2n+2} - 2(-1)^{n+1}\right) = \frac{1}{5}\left(\phi_+^{2n+1}(\phi_+^{-1}+\phi_+) + \phi_-^{2n+1}(\phi_-^{-1}+\phi_-)\right)$ and since $\phi_\pm^{-1} = -\phi_\mp$ we have $=\frac{1}{5}\left(\phi_+-\phi_-\right)\left(\phi_+^{2n+1} - \phi_-^{2n+1}\right) = F_{2n}$.

And I guess something similar for the second equation. Granted, the algebra is ridiculously cumbersome, but it seems to work for me.

share|improve this answer
add comment

These two formula are essentially one set of equations. That is, you can prove them both with one inductive proof. For example, if we know that (i) and (ii), we can proof the $F_{2n+2} = F_{n+1}^2 + F_n^2$. And if we know:

$$F_{2n}=F_n^2+F_{n-1}^2$$ and $$F_{2n-1} = F_{n-2}F_{n-1} + F_{n-1} F_{n}$$

we can show $F_{2n+1} = F_{n-1}F_n + F_n F_{n+1}$

If we know (i) and (ii) for a particular $n$, we write:

$$F_{2n+2} = F_{2n+1} + F_{2n} = F_{n-1}F_n + F_n F_{n+1} + F_n^2 + F_{n-1}^2$$ $$= F_{n-1}(F_n+F_{n-1}) + F_{n+1}F_n + F_n^2 = F_{n-1}F_{n+1} + F_{n+1}F_n + F_n^2 $$ $$= F_{n+1}(F_n + F_{n-1}) + F_n^2 = F_{n+1}^2 + F_n^2$$

In the odd case, if $F_{2n}=F_n^2+F_{n-1}^2$ and $F_{2n-1} = F_{n-2}F_{n-1} + F_{n-1} F_{n}$, we take:

$$F_{2n+1} = F_{2n} + F_{2n-1} = F_n^2 + F_{n-1}^2 + F_{n-2}F_{n-1} + F_nF_{n-1} $$ $$= F_n(F_n+F_{n-1}) + F_{n-1}(F_{n-1}+F_{n-2})=F_n F_{n+1} + F_n F_{n-1}$$

I'll leave it to you to show the intial cases...

share|improve this answer
add comment

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