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.