Fibonacci from golden ratio using power series

While reading about Fibonacci series, I came across the formula which gives the Fibonacci number using golden ratios. I was curious about how did such an equation was derived and how could it give the answer so correctly. This problem introduced me to the world of generating function. I will start with a few definitions.

A formal power series is an expression of the form

a₀ + a₁x + a₂x² + …

where a is a coefficient.

A generating function is a formal power series whose coefficients give the sequence { a₀, a₁, a₂, … }. A general idea is as follows. In counting problems we are often interested in counting the number of objects of size n , which we represent represent as a₀ . By varying n, we get different values of a_n. In this way, we get a sequence of real numbers a₀, a₁, a₂, … 

from which we can define a power series

G(x) = a₀ + a₁x + a₂x² + …

The above G(x) is the generating function for the sequence a₀, a₁, a₂, … 

Let us find an explicit formula for finding nth element of the fibonacci series

First, we will define some useful results.

-ϕ₁ and -ϕ₂ be roots of the equation (x² + x – 1)

ϕ₁ = (1 + √5)/2 and ϕ₂ = (1 – √5)/2
Therefore, ϕ₁ – ϕ₂ = √5  .......(1)
and ϕ₁.ϕ₂ = –1 .........(2)
We know that for a fibonacci number F_n,
F_n = F_n-1 + F_n-2
or F_n – F_n-1 – F_n-2  = 0
F₀ = 0, F₁ = 1.
Let the generating function for F_n be  
F(x) = F₀ + F₁x + F₂x² + F₃x³ + ...
Now, multiplying F(x) with 1, -x and -x² and, adding them
                   F(x) = F₁x + F₂x² + F₃x³ + ...
                –xF(x) =       – F₁x² – F₂x³ –  F₃x⁴ ...
               –x²F(x) =                  – F₁x³– F₂x⁴ – F₃x⁵ ...
_____________________________________________
(1 – x  – x²).F(x) = x    + 0       + 0     + 0 ....

or F(x) = –x/(x² + x – 1)

Using partial fractions, we decompose 

F(x) = A/(x + ϕ₁) + B/(x + ϕ₂)
or –x/(x² + x – 1) = A/(x + ϕ₁) + B/(x + ϕ₂)
or -x = A(x + ϕ₂) + B(x + ϕ₁)
Putting x = -ϕ₂, we have ϕ₂ = B(-ϕ₂ + ϕ₁),
or B = ϕ₂/√5
Putting x = -ϕ₁, we have ϕ₁ = A(-ϕ₁ + ϕ₂),
or A= -ϕ₁/√5


Therefore,
F(x) = (-ϕ₁/√5)/(x + ϕ₁) + (ϕ₂/√5)/(x + ϕ₂)
       = -(1/√5)/(1 + x/ϕ₁) + (1/√5)/(1 + x/ϕ₂)
       = -(1/√5)/(1 - xϕ₂) + (1/√5)/(1 - xϕ₁)             [From 2]

       = -(1/√5)Σ(xϕ₂)n + (1/√5)Σ(xϕ₁)n                 [From the equation for summation of G.P series] 

       = (1/√5)Σ(ϕ₁ⁿ - ϕ₂ⁿ)xⁿ

Therefore, the coefficient of xⁿ will give F_n


Finally, we have

F_n = (1/√5)(ϕ₁ⁿ - ϕ₂ⁿ)

To learn more about generating functions check this out.