# Generating Functions

• If we have an infinite sequence $$a_0,a_1,a_2\ldots$$, then we will say its generating function is $G(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots\,.$
• For example,
• For the sequence $$a_k=k+1$$, the generating function is $$\sum_{k=0}^\infty (k+1)x^k$$.
• For the sequence $$a_k=2\cdot 3^k$$, the generating function is $$\sum_{k=0}^\infty 2\cdot3^k x^k$$.
• For a finite sequence $$a_0,a_1,\ldots,a_k$$, the generating sequence is $G(x)=a_0+a_1x+a_2x^2+\cdots+a_kx^k\,.$
• For the sequence $$a_k=C(n,k)$$ for $$0\le k \le n$$, the generating function is $G(x)=C(n,0)+C(n,1)x+C(n,2)x^2+\cdots+C(n,n)x^n\,.$ By the binomial theorem, this is $$(1+x)^n$$.

# Solving Recurrences

• So far, generating functions are just a weird mathematical notation trick.
• Suppose we have a recurrence relation $$a_k=3a_{k-1}$$ with $$a_0=2$$.
• Whatever the solution to that is, we know it has a generating function $$G(x)=\sum_{k=0}^\infty a_kx^k$$.
• First notice that $xG(x) = \sum_{k=0}^\infty a_kx^{k+1} = \sum_{j=1}^\infty a_{j-1}x^{j}\,.$
• Now we can get \begin{align*} G(x)-3xG(x) &= \sum_{k=0}^\infty a_kx^k - 3\sum_{k=1}^\infty a_{k-1}x^{k} \\ &= a_0 + \sum_{k=1}^\infty (a_k-3a_{k-1})x^k \\ &= a_0=2\,. \end{align*}
• Now, we get \begin{align*} G(x)-3xG(x) &= 2 \\ G(x) &= \frac{2}{1-3x}\,. \end{align*}
• If only we could turn that into a polynomial, we could read off the solution from the coefficients.
• What luck! The book has a table of useful generating function identities, and we get $G(x)= \frac{2}{1-3x} = 2\sum_{k=0}^{\infty} 3^kx^k= \sum_{k=0}^{\infty} 2\cdot 3^kx^k\,.$
• So, $$a_k=2\cdot 3^k$$.
• Sure, we could have guessed that one some other way, but these generating functions might actually be useful for something.
• Let's try another: $$a_n=2a_{n-1}+4$$ with $$a_0=4$$. Again, let $$G(x)$$ be the generating function for the sequence.
• Again, let $$G(x)=\sum_{k=0}^\infty a_kx^k$$ be the generating function for this sequence.
• Now, \begin{align*} G(x)-2xG(x) &= \sum_{k=0}^\infty a_kx^k - 2\sum_{k=1}^\infty a_{k-1}x^k \\ G(x)-2xG(x) &= a_0x^0 + \sum_{k=1}^\infty (a_k - 2a_{k-1})x^k \\ G(x)-2xG(x) &= 4 + \sum_{k=1}^\infty 4x^k \\ G(x)(1-2x) &= 4-4+\sum_{k=0}^\infty 4x^k \\ G(x) &= \frac{1}{1-2x} \sum_{k=0}^\infty 4x^k\,. \end{align*}
• Again, we look at the table of generating function identities and find something useful: \begin{align*} G(x) &= \frac{1}{1-2x} \sum_{k=0}^\infty 4x^k \\ &= \sum_{k=0}^\infty 2^kx^k \cdot \sum_{k=0}^\infty 4x^k\,. \end{align*}
• If we can rearrange this to get the $$x^k$$ coefficients, we're done. In fact, \begin{align*} G(x) &= \sum_{k=0}^\infty 2^kx^k \cdot \sum_{k=0}^\infty 4x^k \\ &= \sum_{k=0}^\infty \left( \sum_{j=0}^k 4\cdot 2^j \right)x^k\,. \end{align*}
• Finally, the coefficient of the $$x^k$$ term in this is $a_k=\sum_{j=0}^k 4\cdot 2^j = 4\sum_{j=0}^k 2^j = 4(2^k-1) = 2^k-4\,.$
• Theorem: If we have two generating functions $$f(x)=\sum_{k=0}^{\infty} a_k x^k$$ and $$g(x)=\sum_{k=0}^{\infty} b_k x^k$$, then $f(x)+g(x)=\sum_{k=0}^{\infty} (a_k+b_k) x^k\,,\\ f(x)\cdot g(x)=\sum_{k=0}^{\infty} \left( \sum_{j=0}^{k} a_j b_{k-j} \right) x^k\,.$

• This theorem can be used (as we did above) to combine (what looks like) multiple generating functions into one.
• Generating functions can also be used to solve some counting problems.
• Honestly, at this level they're more trouble than they are worth.
• If you're interested, see the textbook.