TAOCP 1.2.9 Exercise 1

Section 1.2.9: Generating Functions

Exercise 1. [M12] What is the generating function for the sequence $2,5,13,35,\ldots = \langle 2^n+3^n \rangle$?

Verified: no
Solve time: -

Solution

Let $G(z)$ be the generating function for the sequence

$$ \langle 2^n+3^n\rangle = 2,5,13,35,\ldots. $$

By definition,

$$ G(z)=\sum_{n\ge0}(2^n+3^n)z^n. $$

Using operation A, Eq. (2), we split this into two generating functions:

$$ G(z)=\sum_{n\ge0}2^nz^n+\sum_{n\ge0}3^nz^n. $$

Since

$$ 2^nz^n=(2z)^n, \qquad 3^nz^n=(3z)^n, $$

Eq. (5) gives

$$ \sum_{n\ge0}(2z)^n=\frac1{1-2z}, \qquad \sum_{n\ge0}(3z)^n=\frac1{1-3z}. $$

Therefore

$$ G(z)=\frac1{1-2z}+\frac1{1-3z}. $$

Combining the fractions,

$$ G(z) = \frac{(1-3z)+(1-2z)}{(1-2z)(1-3z)} = \frac{2-5z}{(1-2z)(1-3z)}. $$

Hence the generating function is

$$ \boxed{ G(z)=\frac1{1-2z}+\frac1{1-3z} =\frac{2-5z}{(1-2z)(1-3z)} }. $$