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

Question

6224 views around the world

You can reuse this answer
Creative Commons License

Answer 1 · 2015-09-13T08:52:53

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

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#