Proving Fibonacci Identites 
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!
 A: 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.
A: 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$$
A: 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...
