Recurrence Relations and Generating Functions

Generating Functions

Given a series of numbers ${\{a_n\}}_{n=0}^{\infty }$ its generating function in a formal power series $f(x)={\sum }_{n=0}^{\infty }{b}_n{x}^n$ where $b_n$ could be directly obtained from $a_n$ and $n$

Ordinary generating functions have $b_n=a_n$

Solving Recurrences

example recurrence

for $n\ge 2$ and $f_0=0$, $f_1=1$

$$f_n=f_{n-1}+f_{n-2}$$

1. Form generating function:

$$F(x)=f_0+f_{1}x+f_2{x}^2+f_3{x}^3+\dots$$

2. Manipulation: substitute known values and recurrences

$$\begin{array}{rl}F(x)& =0+1x+(f_1+f_0)x^2+(f_2+f_1)x^3+\dots \\ & =x+x(f_{1}x+f_2{x}^2+\dots )+x^2(f_0+f_{1}x+f_2{x}^2+\dots )\\ & =x+xF(x)+x^{2}F(x)\end{array}$$

which gives us

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

example 2:

for $a_1=2$

$$a_{i+1}=a_i+2i$$

for generating function and manipulate

$$\begin{array}{rl}A(x)& =2x+(a_1+2)x^2+(a_2+2\cdot 2)x^3+\dots \\ A(x)& =2x+xA(x)+2x^2(1+2x+3x^2+\dots )\\ A(x)& =xA(x)+2x(1+x+2x^2+3x^3+\dots )\end{array}$$

Sum of Power Series

From the sum of GP we can derive the sum of a power series to get

$$\sum ^{\infty }n{x}^n=\frac{1}{(1-x{)}^2}$$

$$\begin{array}{rl}A(x)& =xA(x)+\frac{2x}{(1-x{)}^2}\\ A(x)& =\frac{2x}{(1-x{)}^3}\end{array}$$