Can you prove the Fibonacci Sequence property?

[FeDeX_LaTeX]

Prove that:

F_{n} = \frac {\varphi^n - (1-\varphi)^n}{\sqrt5}

holds true for any number in the Fibonacci Sequence.

Who can answer the fastest?

 

[Char. Limit]

Hmm... well, defining phi as (1+sqrt(5))/2, this means that the second term there is equal to -(phi+1), or -1/phi.

So... for odd n, the denominator reduces to phi^n+phi^-n. Multiplying top and bottom by phi^n gives us phi^2n+1 in the numerator and sqrt(5)*phi^n in the denominator. Splitting the fraction gives us (phi^n)/sqrt(5) + 1/(sqrt(5)*phi^n). Beyond there... I don't know.

 

[Gerenuk]

F_n+F_{n+1}=\frac{1}{\sqrt{5}}\left(\phi^n-(1-\phi)^n+\phi^{n+1}-(1-\phi)^{n+1}\right)=\frac{1}{\sqrt{5}}\left(\phi^n(1+\phi)-(1-\phi)^{n}(2-\phi)\right)
Since by definition
\phi+1=\phi^2
and we also get
(1-\phi)^2=1-2\phi+\phi^2=2-\phi
then
F_n+F_{n+1}=\frac{1}{\sqrt{5}}\left(\phi^n\phi^2-(1-\phi)^{n}(1-\phi)^2\right)=\frac{1}{\sqrt{5}}\left(\phi^{n+2}-(1-\phi)^{n+2}\right)=F_{n+2}
That's all you need.