# 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.