TAOCP 1.2.9 Exercise 22

Exercise 22. [M21] Find a generating function $G(z)$ for which

$$ [z^n]G(z) = \sum_{k_0+2k_1+4k_2+8k_3+\cdots=n} \binom{r}{k_0}\binom{r}{k_1}\binom{r}{k_2}\binom{r}{k_3}\cdots . $$

Verified: yes
Solve time: 1m05s

Solution

We are asked to find a generating function $G(z)$ such that the coefficient of $z^n$ is

$$ [z^n]G(z) = \sum_{k_0+2k_1+4k_2+8k_3+\cdots=n} \binom{r}{k_0}\binom{r}{k_1}\binom{r}{k_2}\binom{r}{k_3}\cdots. $$

Observe that the sum runs over all sequences of nonnegative integers $(k_0,k_1,k_2,\ldots)$ such that

$$ \sum_{j \ge 0} 2^j k_j = n. $$

For each fixed $j$, the factor $\binom{r}{k_j}$ suggests the generating function for $k_j$ is, by the binomial theorem (Eq. (19)),

$$ \sum_{k_j \ge 0} \binom{r}{k_j} (z^{2^j})^{k_j} = (1+z^{2^j})^r. $$

This is because $k_j$ contributes $2^j k_j$ to the exponent of $z$, and the sum over $k_j$ is exactly the binomial expansion of $(1+z^{2^j})^r$.

Since the $k_j$ are independent for different $j$, the overall generating function is the product over all $j \ge 0$:

$$ G(z) = \prod_{j \ge 0} (1+z^{2^j})^r. $$

To verify, expand each factor:

$$ (1+z^{2^j})^r = \sum_{k_j \ge 0} \binom{r}{k_j} z^{2^j k_j}. $$

Then, by the rule for products of generating functions (Eq. (9)), the coefficient of $z^n$ in the product is

$$ [z^n] G(z) = \sum_{k_0,k_1,k_2,\ldots \ge 0 \atop k_0+2k_1+4k_2+\cdots = n} \binom{r}{k_0}\binom{r}{k_1}\binom{r}{k_2}\cdots, $$

which is exactly the expression required. This completes the proof.

∎

The final generating function is

$$ \boxed{G(z) = \prod_{j \ge 0} (1+z^{2^j})^r}. $$