# Generating Functions: linking Sequence & Series

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.

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.

http://www.amazon.co.uk/dp/0983951306/ref=cm_sw_r_udp_awd_UKSvtb1AXNWCE

Advertisements