The Fibonacci sequence is defined by the recurrence relation (sometimes called 'difference equation')
Fn + Fn+1=Fn+2.
This is the simplest possible second order recurrence relation with constant coefficients as all the coefficients are one. The method of solving recurrence relations like this is to let Fn=xn. Then xn+xn+1=xn+2 and hence (dividing by xn), 1 + x = x2 giving the quadratic equation x2-x-1=0. So the quadratic equation has solutions
x= 1 ±Ö5
2

. Hence the solutions of the recurrence relation are
Fn=A æ
ç
è 		1+Ö5
2
 ö
÷
ø 		n

 
 +B æ
ç
è 		1-Ö5
2
 ö
÷
ø 		n

 
where we have to find the values of the constants A and B.

Putting n=1 and F1 = 1 and multiplying by 2
2 = A(1 + Ö5)+B(1-Ö5)
and putting n=2 and F2=1 and multiplying by 4
4 = A(1 + Ö5)2 + B(1-Ö5)2.
Solving these simultaneous equations for A and B we get
A= 1
Ö5
 ,     B = - 1
Ö5
 .
Hence the solution of the recurrence relation is
Fn = 1
Ö5
 æ
ç
è 		1+Ö5
2
 ö
÷
ø 		n

 
 - 1
Ö5
 æ
ç
è 		1-Ö5
2
 ö
÷
ø 		n

 
 .

Note that the formula for Fn is given in terms of the roots of the quadratic equation x2-x-1=0 and one of the roots is the Golden Ratio which accounts for the many connections between Fibonacci numbers and the Golden Ratio.

This problem complements the material in the article
The Golden Ratio, Fibonacci Numbers and Continued Fractions

For a sequence of, mainly more elementary, problems on these topics see Golden Mathematics