Derivation of Fibonacci closed form

[MathAmateur]

See below

 

[HallsofIvy]

If you "look for" a solutions of the form f_n= \rho c^n, as your book suggests, put that into f_n= f_{n-1}+ f_{n+ 1} you get
\rho c^n= \rho c^{n-1}+ \rho c^{n-2}
Divide through by \rho c^{n-2} and you get
c^{n-(n-2)}= c^{n-1-(n-2)}+ 1
c^2= c+ 1
so that
c^2- c- 1= 0[/itex]<br /> <br /> Complete the square or use the quadratic formula to solve for c and then put it back into f_n= \rho c^n.

 

[MathAmateur]

Homework Statement

I need to understand a derivation of the closed form of the Fibonacci sequence.

Homework Equations

The Fibonacci sequence of course is:
f_n = f_{n-1} + f_{n-2}

The book says the key is to look for solutions of the form

f_n = {c}{\rho}^n

for some constants c and and \rho. The recurrence relation
f_n = f_{n-1} + f_{n-2}

becomes

\rho^2 = \rho + 1.

There are two possilbe values of \rho, namely \phi and
1 - \phi. The general solution to the recurrance is

f_n = c_{1} {\phi}_n+ c_{2}(1-{\phi})^n

where \phiis the golden ratio 1.6180339


So where did the book get this? Can anyone explain this.

 

[MathAmateur]

Thanks Halls. Now it is clear.