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