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
a0 + a1x + a2x2 + …
where a is a coefficient.
A generating function is a formal power series whose coefficients give the sequence { a0, a1, a2, … }. 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 a0 . By varying n, we get different values of an. In this way, we get a sequence of real numbers a0, a1, a2, …
from which we can define a power series
G(x) = a0 + a1x + a2x2 + …
The above G(x) is the generating function for the sequence a0, a1, a2, …
ϕ1 = (1 + √5)/2 and ϕ2 = (1 – √5)/2
Therefore, ϕ1 – ϕ2 = √5 .......(1)
and ϕ1.ϕ2 = –1 .........(2)
We know that for a fibonacci number Fn,
Fn = Fn-1 + Fn-2
or Fn – Fn-1 – Fn-2 = 0
F0 = 0, F1 = 1.
Let the generating function for Fn be
F(x) = F0 + F1x + F2x2 + F3x3 + ...
Now, multiplying F(x) with 1, -x and -x2 and, adding them
F(x) = F1x + F2x2 + F3x3 + ...
–xF(x) = – F1x2 – F2x3 – F3x4 ...
–x2F(x) = – F1x3– F2x4 – F3x5 ...
_____________________________________________
(1 – x – x2).F(x) = x + 0 + 0 + 0 ....
Therefore, ϕ1 – ϕ2 = √5 .......(1)
and ϕ1.ϕ2 = –1 .........(2)
We know that for a fibonacci number Fn,
Fn = Fn-1 + Fn-2
or Fn – Fn-1 – Fn-2 = 0
F0 = 0, F1 = 1.
Let the generating function for Fn be
F(x) = F0 + F1x + F2x2 + F3x3 + ...
Now, multiplying F(x) with 1, -x and -x2 and, adding them
F(x) = F1x + F2x2 +
–xF(x) = – F1x2 – F2x3 – F3x4 ...
–x2F(x) = – F1x3– F2x4 – F3x5 ...
_____________________________________________
(1 – x – x2).F(x) = x + 0 + 0 + 0 ....
or F(x) = –x/(x2 + x – 1)
Using partial fractions, we decompose
F(x) = A/(x + ϕ1) + B/(x + ϕ2)
or –x/(x2 + x – 1) = A/(x + ϕ1) + B/(x + ϕ2)
or -x = A(x + ϕ2) + B(x + ϕ1)
Putting x = -ϕ2, we have ϕ2 = B(-ϕ2 + ϕ1),
or B = ϕ2/√5
Putting x = -ϕ1, we have ϕ1 = A(-ϕ1 + ϕ2),
or A= -ϕ1/√5
Therefore,
F(x) = (-ϕ1/√5)/(x + ϕ1) + (ϕ2/√5)/(x + ϕ2)
= -(1/√5)/(1 + x/ϕ1) + (1/√5)/(1 + x/ϕ2)
= -(1/√5)/(1 - xϕ2) + (1/√5)/(1 - xϕ1) [From 2]
Finally, we have
or –x/(x2 + x – 1) = A/(x + ϕ1) + B/(x + ϕ2)
or -x = A(x + ϕ2) + B(x + ϕ1)
Putting x = -ϕ2, we have ϕ2 = B(-ϕ2 + ϕ1),
or B = ϕ2/√5
Putting x = -ϕ1, we have ϕ1 = A(-ϕ1 + ϕ2),
or A= -ϕ1/√5
Therefore,
F(x) = (-ϕ1/√5)/(x + ϕ1) + (ϕ2/√5)/(x + ϕ2)
= -(1/√5)/(1 + x/ϕ1) + (1/√5)/(1 + x/ϕ2)
= -(1/√5)/(1 - xϕ2) + (1/√5)/(1 - xϕ1) [From 2]
= -(1/√5)Σ(xϕ2)n + (1/√5)Σ(xϕ1)n [From the equation for summation of G.P series]
Finally, we have
