Discrete Math Home

## Generating Functions

In this section, we study generating functions as a tool for solving recurrence relations.

Definition (Generating function). The generating function for the sequence $$\{a_n\}$$ is a function $$f$$ defined as the following power series $f(x)=\sum_{n=0}^{\infty} a_nx^n=a_0+a_1x+a_2x^2+a_3x^3+\cdots,$ where the domain of $$f$$ is the interval of convergence of the power series $$\displaystyle \sum_{n=0}^{\infty} a_nx^n$$.

Example.

1. Consider the constant sequence $$\{a_n\}$$ where $$a_n=1$$ for all $$n\geq 0$$. The corresponding power series is $\sum_{n=0}^{\infty} a_nx^n=\sum_{n=0}^{\infty} x^n=1+x+x^2+x^3+\cdots,$ which converges to $$\displaystyle\frac{1}{1-x}$$ when $$|x|<1$$. Thus the generating function for the constant sequence $$\{1\}$$ is $f(x)=\displaystyle\frac{1}{1-x}$ with domain $$(-1,1)$$.

2. Consider the sequence $$\{a_n\}$$ where $$a_n=\frac{1}{n!}$$ for all $$n\geq 0$$. The corresponding power series is $\sum_{n=0}^{\infty} a_nx^n=\sum_{n=0}^{\infty} \frac{x^n}{n!}=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots,$ which converges to $$e^x$$ for all real $$x$$. Thus the generating function for the sequence $$\{\frac{1}{n!}\}$$ is $f(x)=e^x$ with domain $$(-\infty,\infty)$$.

Now we show by examples how generating functions can be used to solve recurrence relations.

Example. Use a generating function to solve the following recurrence relation. $a_n=2a_{n-1}+1,\; a_0=0$ Solution. First we rewrite the recurrence relation in the following form: $a_{n+1}=2a_n+1,n\geq 0,\; a_0=0$ Suppose $$f(x)=\displaystyle\sum_{n=0}^{\infty} a_nx^n$$ for all $$x$$ that are to be determined. Multiplying both sides of the recurrence relation $$a_{n+1}=2a_n+1$$ by $$x^n$$ and taking summation over $$n$$ from $$0$$ to $$\infty$$, we get \begin{align*} &\sum_{n=0}^{\infty} a_{n+1}x^n=\sum_{n=0}^{\infty}(2a_n+1)x^n\\ \implies & \sum_{n=0}^{\infty} a_{n+1} x^{n+1}=2x\sum_{n=0}^{\infty}a_nx^n+x\sum_{n=0}^{\infty} x^n \;(\text{multiplying both sides by } x)\\ \implies & -a_0+\sum_{n=0}^{\infty} a_nx^{n} =2xf(x)+\frac{x}{1-x} \;(\text{where } |x|<1)\\ \implies & f(x)=2xf(x)+\frac{x}{1-x} \;(\text{since } a_0=0)\\ \implies & f(x)=\frac{x}{(1-x)(1-2x)}. \end{align*} Now we write a power series for the generating function $$f$$ as follows: \begin{align*} f(x) &=\frac{x}{(1-x)(1-2x)}\\ &=x\left( \frac{2}{1-2x}-\frac{1}{1-x} \right)\\ &=x\left( 2\sum_{n=0}^{\infty} (2x)^n - \sum_{n=0}^{\infty} x^n\right) \;\left(\text{where } |x|<\frac{1}{2} \right)\\ &=x\sum_{n=0}^{\infty} (2^{n+1}-1)x^n\\ &=\sum_{n=0}^{\infty} (2^{n+1}-1)x^{n+1}\\ &=\sum_{n=1}^{\infty} (2^n-1)x^n \end{align*} Thus $$a_n=2^n-1$$ for all $$n\geq 0$$. Note that the domain of the generating function $$f$$ is $$\left( -\frac{1}{2},\frac{1}{2} \right)$$.

Example. Use a generating function to find an explicit formula for the $$n$$th term of the Fibonacci sequence $$\{F_n\}$$ which is given by the following recurrence relation: $F_n=F_{n-1}+F_{n-2},\; n\geq 2;\; F_0=0,\; F_1=1$ Solution. First we rewrite the recurrence relation in the following form: $F_{n+2}=F_{n+1}+F_n,\; n\geq 0;\; F_0=0,\; F_1=1$ Suppose $$f(x)=\displaystyle\sum_{n=0}^{\infty} F_{n}x^n$$ for all $$x$$ that are to be determined. Multiplying both sides of the recurrence relation $$F_{n+2}=F_{n+1}+F_n$$ by $$x^n$$ and taking summation over $$n$$ from $$0$$ to $$\infty$$, we get \begin{align*} &\sum_{n=0}^{\infty} F_{n+2}x^n=\sum_{n=0}^{\infty}(F_{n+1}+F_n)x^n\\ \implies & \sum_{n=0}^{\infty} F_{n+2} x^{n+2}=x\sum_{n=0}^{\infty}F_{n+1}x^{n+1}+x^2\sum_{n=0}^{\infty} F_{n} x^n \;(\text{multiplying both sides by } x^2)\\ \implies & -F_0-F_1x+\sum_{n=0}^{\infty} F_nx^{n} =x\left( -F_0+\sum_{n=0}^{\infty} F_nx^{n}\right)+ x^2f(x) \\ \implies & -x+f(x)=xf(x)+ x^2f(x) \;(\text{since } F_0=0, F_1=1)\\ \implies & f(x)=\frac{x}{1-x-x^2}. \end{align*} Now we write a power series for the generating function $$f$$ as follows: \begin{align*} f(x) &=\frac{x}{1-x-x^2}\\ &=\frac{1}{r_1-r_2} \left( \frac{1}{1-xr_1}-\frac{1}{1-xr_2} \right) \;\left(\text{where } r_1,r_2=\frac{1\pm \sqrt{5}}{2}\right)\\ &=\frac{1}{\sqrt{5}}\left( \sum_{n=0}^{\infty} r_1^n x^n - \sum_{n=0}^{\infty} r_2^n x^n\right) \;\left(\text{where } |x|<\frac{1}{r_1} \right)\\ &=\frac{1}{\sqrt{5}} \sum_{n=0}^{\infty} (r_1^n - r_2^n) x^n\\ &=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty} \left(\left( \frac{1+ \sqrt{5}}{2}\right)^n-\left( \frac{1- \sqrt{5}}{2}\right)^n \right) x^n \end{align*} Thus $$F_n=\frac{1}{\sqrt{5}}\left(\left( \frac{1+ \sqrt{5}}{2}\right)^n-\left( \frac{1- \sqrt{5}}{2}\right)^n \right)$$ for all $$n\geq 0$$. Note that the domain of the generating function $$f$$ is $$\left( -\frac{2}{1+ \sqrt{5}},\frac{2}{1+ \sqrt{5}} \right)$$.

Last edited