Generating Functions: linking Sequence & Series

Modern Math 1 Comment

Donald Knuth, et al:
“The most powerful way to deal with sequences of numbers, …, is to manipulate infinite series that generate those sequences.” – “Concrete Mathematics“

“…to discover the equation in the first place, using the important method of generating functions, which is a valuable technique for solving so many problems.” – “The Art of Computer Programming Volume I”

Example:
Fibonacci sequence: {0, 1, 1, 2, 3, 5, 8, 13…}

Definition of the Fibonacci sequence as a recurrence relation:
\boxed{ F_{n}= \begin{cases} 0, & \text{for }n=0\\ 1, & \text{for }n=1\\ F_{n-2} + F_{n-1} , & \text{for } n \geq { 2} \end{cases} }

This definition is not so useful in computation, we want to find a general term formula F_{n} in terms of n.

image

Step 1: Find the generating function F(x)

The correspondence below:
Sequence \leftrightarrow Generating Function

\left \{ F_{0}, F_{1}, F_{2}, ..., F_{n} \right \} \leftrightarrow F(x)
with
F(x) = F_{0}x^{0} + F_{1}x^{1} + F_{2}x^{2} + ...+ F_{n}x^{n}

Step 2: Find the closed form of F(x)

[A]: F(x)x^2 = F_{0}x^2 + F_{1}x^3 + F_{2}x^4 + ...

[B]: F(x)x^1 = F_{0}x^1 + F_{1}x^2 + F_{2}x^3 + F_{3}x^4 + ...

[C]: F(x)x^0 = F_{0}x^0+ F_{1}x^1 + F_{2}x^2 + F_{3}x^3 + F_{4}x^4 ...

[A] + [B] – [C]:

Left-Hand Side:
F(x)(x^2+x^1-x^0)

Right-Hand Side:
F_{0}x^{1} - F_{0}x^{0} - F_{1}x^{1}
+ (F_{0}+F_{1} - F_{2})x^2
+ (F_{1}+F_{2} - F_{3})x^3
+ (F_{2}+F_{3} - F_{4})x^4
+ …
+ (F_{n-2}+F_{n-1} - F_{n})x^n
+ …

From the Recurrence definition above, we know:
F_{0} = 0, F_{1} = 1
and
F_{n} = F_{n-2}+F_{n-1}
or,
F_{n-2}+F_{n-1} - F_{n} = 0

Right-Hand Side: -x

We get [A] + [B] – [C]:
F(x)(x^2+x^1-x^0) = -x

\boxed {F(x) = \frac {x}{1-x-x^2} }

Step 3: Find the general term Fn

Now we have a generating function of the Fibonacci Sequence F(x) in closed form. We want to express it as an infinite Series.

Let’s factorize
1-x-x^2 = (1-rx)(1-sx)
F(x) = \frac {x}{1-x-x^2} = \frac {x}{ (1-rx)(1-sx) }
F(x) = \frac {R}{1-rx} + \frac {S}{1-sx}
F(x) = \frac { (R+S)- (rS+ sR)x }{ 1-(r+s)x +rsx^2 }

\frac {x}{1-x-x^2} = \frac { (R+S)- (rS+ sR)x }{ 1-(r+s)x +rsx^2 }

Matching term by term on both sides, solve the 4 simultaneous equations with 4 unknowns:
\begin{cases} R+S= 0, & \\ rS+sR=-1, & \\ r+s =1, & \\ rs =-1, & \end{cases}
R = \frac {1}{r-s}
S = -\frac {1}{r-s}

F(x) = \frac {R}{1-rx} + \frac {S}{1-sx} = \frac {1}{r-s} (\frac {1}{1-rs} - \frac {1}{1-sx})

We know in secondary school:
\frac {1}{1-u} = 1+u+u^2+u^3+...+u^n+...

Let u = rx
\frac {1}{1-rx} = 1+rx+r^2x^2+r^3x^3+...+r^nx^n+...
Similarly,
\frac {1}{1-sx} = 1+sx+s^2x^2+s^3x^3+...+s^nx^n+...

F(x) = \frac {1}{r-s} (\frac {1}{1-rs} - \frac {1}{1-sx})
F(x) = \frac {1}{r-s} \left ((r-s)x + (r^2-s^2)x^2 +... (r^n-s^n)x^n+... \right)

F(x) = \underbrace {0 }_{F_{0}} + \underbrace { \frac {r-s}{r-s}}_{F_{1}}x + \underbrace { \frac {r^2-s^2}{r-s}}_{F_{2}}x^2 +... \underbrace { \frac {r^n-s^n}{r-s}}_{F_{n}}x^n+...

F_{n} = \frac {r^n-s^n}{r-s}

From the above 2 equations in r, s:
\begin{cases} r+s =1, & \\ rs =-1, & \end{cases}
By 趙爽 Zhao Shuang 三国东吴 : 222 AD Chinese Mathematician (1,300 years earlier than Viète, 16th Century French Mathematician) Theorem: r, s are the solutions of the quadratic equation:
y^2 -(r+s)y +rs = 0
y^2 - y -1 = 0
y= \frac{1 \pm \sqrt{5}}{2}
We assume r > s,
\begin{cases} r= \frac{1 + \sqrt{5}}{2} , \text {(this is golden ratio)} & \\ s = \frac{1 - \sqrt{5}}{2} & \end{cases}
r - s = \sqrt{5}

F_{n} = \frac {r^n-s^n}{r- s}

\boxed { F_{n}= \frac{1} {\sqrt {5}}\left(\bigl( \frac {1+ \sqrt {5}}{2} \bigr)^n - \bigl( \frac {1-\sqrt {5}}{2} \bigr)^n\right) }

Verify:
F_{0} = 0
F_{1} = \frac{1} {\sqrt {5}}\left(\bigl( \frac {1+ \sqrt {5}}{2} \bigr)^1 - \bigl( \frac {1-\sqrt {5}}{2} \bigr)^1 \right) = \frac {\sqrt {5}} {\sqrt {5}}= 1
F_{2} = \frac{1} {\sqrt {5}}\left(\bigl( \frac {1+ \sqrt {5}}{2} \bigr)^2 - \bigl( \frac {1-\sqrt {5}}{2} \bigr)^2 \right) = \frac {4\sqrt {5}} {4\sqrt {5}} = 1
F_{3} = \frac{1} {\sqrt {5}}\left(\bigl( \frac {1+ \sqrt {5}}{2} \bigr)^3 - \bigl( \frac {1-\sqrt {5}}{2} \bigr)^3\right) = \frac {16\sqrt {5}} {8\sqrt {5}} = 2
F_{4} = \frac{1} {\sqrt {5}}\left(\bigl( \frac {1+ \sqrt {5}}{2} \bigr)^4 - \bigl( \frac {1-\sqrt {5}}{2} \bigr)^4\right) = \frac {48\sqrt {5}} {16\sqrt {5}} = 3

Ref:
Math Girls by Hiroshi Yuki et al.

One thought on “Generating Functions: linking Sequence & Series”

Leave a comment