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
[tex]c^2- c- 1= 0[/itex]

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 $$\phi$$is the golden ratio 1.6180339


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

 

[MathAmateur]

Thanks Halls. Now it is clear.