Here is another excellent solution from Andrei of Tudor Vianu National College, Bucharest, Romania.

We are given Fn = 1 5 ( αn - βn ) where α and β are solutions of the quadratic equation x2 -x-1=0 and α>β.

(1) In the quadratic equation ax2 +bx+c=0 with roots α amd β, using Viete's relations for the sum and product of the roots, I obtain: αβ=-b/a, α+β=c/a
In the particular case of the equation x2 -x-1=0, I have: αβ=-1, α+β=1
(2)
1 α + 1 α2 = α+1 α2 =1

as α satisfies x2 =x+1. Similarly for β.

(3) Here I shall prove that F1 =1, F2 =1 and Fn + Fn+1 = Fn+2 and hence Fn is the nth Fibonacci number. First, I calculate α and β: α= 1+5 2 and α= 1+5 2


F1 = 1 5 ( 1+5 2 - 1-5 2 )=1 F2 = 1 5 ( α2 - β2 )= 1 5 (α-β)(α+β)=1 Fn + Fn+1 - Fn+2 = 1 5 [ αn - βn + αn+1 - βn+1 - αn+2 + βn+2 ] Fn + Fn+1 - Fn+2 = 1 5 [- αn ( α2 -α-1)+ βn ( β2 -β-1)]=0

(4) I shall prove by induction the statement Pn that 1+ F1 + F2 + Fn = Fn+2 .

I know that F1 =1, F2 =1 and by (3), F3 =2, F4 =3, F5 =5, F6 =8,...
For n=1, P1 is 1+ F1 = F3 which is evidently true as 1 + 1 = 2.
For n=2, P1 is 1+ F1 + F2 = F4 which is evidently true as 1 + 1 + 1 = 3.
For n=3, P1 is 1+ F1 + F2 + F3 = F5 which is evidently true as 1 + 1 + 1 + 2 = 5.

Now I assume that P(k) is true for a fixed k and I shall prove that P(k+1) is also true, that is:
Pk :1+ F1 + F2 + Fk = Fk+2 Pk+1 :1+ F1 + F2 + Fk + Fk+1 = Fk+3


1+ F1 + F2 + Fk + Fk+1 =(1+ F1 + F2 + Fk )+ Fk+1 = Fk+2 + Fk+1 = Fk+3

and hence the result is true for n=k+1. By the principle of mathematical induction the statement Pn is true for all positive integer values of n which completes the proof.