1
$\begingroup$

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!

  • 0
    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.2011-06-05

3 Answers 3

2

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

2

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.

2

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$

  • 0
    thank you! That helped me a lot!2011-06-06