Question

How do I find the `n`th term of the Fibonacci sequence?

Answer 1

If `F_0 = 0` and `F_1 = 1`, then `F_n = (phi^n - (-phi)^(-n))/sqrt(5)`, where `phi = (1+sqrt(5))/2`

Explanation:

I will assume that you are familiar with the definition of the Fibonacci sequence:

`F_0 = 0`, `F_1 = 1`, `F_n = F_(n-2) + F_(n-1)`

yielding:

`0, 1, 1, 2, 3, 5, 8, 13, 21,...`
`color(white)()`

Let's prove this formula by induction:

Let `f(n) = (phi^n - (-phi)^(-n))/sqrt(5)`

First note:

`1/phi = 2/(1+sqrt(5)) = (2(sqrt(5)-1))/((sqrt(5) - 1)(sqrt(5) + 1))`

`= (2(sqrt(5)-1))/(5-1) = (sqrt(5)-1)/2`

and

`phi^2 = ((1+sqrt(5))(1+sqrt(5)))/4 = (1+2sqrt(5)+5)/4`

`= (3+sqrt(5))/2 = (1+sqrt(5))/2 + 1 = phi + 1`

so `phi^2 - phi - 1 = 0`

Base case

`f(0) = (phi^0-(-phi)^(-0))/sqrt(5) = (1-1)/sqrt(5) = 0 = F_0`

`f(1) = (phi^1-(-phi)^(-1))/sqrt(5) = ((1+sqrt(5))/2 - (-(sqrt(5)-1)/2))/sqrt(5) = 1 = F_1`

Induction step

Suppose `F_(n-2) = f(n-2)` and `F_(n-1) = f(n-1)`

Then:

`sqrt(5)(f(n) - f(n-1) - f(n-2))`

`= (phi^n - (-phi)^(-n)) - (phi^(n-1) - (-phi)^(-(n-1))) - (phi^(n-2) - (-phi)^(-(n-2)))`

`= (phi^n-phi^(n-1)-phi^(n-2)) - (-1)^n(phi^-n + phi^(-(n-1)) - phi^(-(n-2)))`

`= phi^(n-2)(phi^2-phi-1) + (-1)^n phi^(-n)(phi^2-phi-1)= 0`

So `f(n) = f(n-2) + f(n-1) = F_(n-2) + F_(n-1) = F_n`