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#