• 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 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\).

• 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\).

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

• Honestly, at this level they're more trouble than they are worth.
• If you're interested, see the textbook.