Calculate the nth term of the Fibonacci Sequence

357 Views Asked by At

The polynomial for the Fibonacci recurrence $F(n) = F(n-1) + F(n-2)$ is

$$x^{2} = x + 1.$$

The solutions are :
$ϕ = \frac{1+\sqrt 5}{2}$ and $ψ = \frac{1-\sqrt 5}{2}.$

So the Fibonacci sequence, for real number has the form $F(n) = u ϕ^{n} + v ψ^{n}$.

With the boundary conditions $F(0) = 0$ one can see that $u = -v$.

The second boundary condition $F(1) = 1$ leads to $1 = u ϕ^{1} + v ψ^{1}$.

Substituting $v$ and simplifying the equation leads to $1 = u\sqrt 5$.

Therefore $u = \frac{1}{\sqrt 5}$ and $v = -\frac{1}{\sqrt 5}$

As a result $$F(n) = \frac{ϕ^{n} - ψ^{n}}{\sqrt 5}.$$

Is there any other way to derive this formula ?