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