Generating functions for compositions

Question

Let $g(n)$ be the number of compositions of n where each part is an odd number. Let $h(n)$ number of compositions of $n$ where each part is either 1 or 2. Using the ordinary generating functions $G(x)$ and $H(x)$, show that $g(n) = h(n-1)$

Answer 1

Here are the steps which are quite simple.

We have by inspection that $$g_n = [z^n] \sum_{k=1}^n \left(\frac{z}{1-z^2}\right)^k$$ and that $$h_n = [z^n] \sum_{k=1}^n \left(z+z^2\right)^k.$$

Now observe that in both cases the terms being summed start at $z$ and hence their powers start at $k$. That means we can extend both sums to infinity without affecting the coefficient of $z^n$ to obtain

$$g_n = [z^n] \sum_{k=1}^\infty \left(\frac{z}{1-z^2}\right)^k$$ and that $$h_n = [z^n] \sum_{k=1}^\infty \left(z+z^2\right)^k.$$

These are both geometric series and we have $$G(z) = \frac{z}{1-z^2} \frac{1}{1-z/(1-z^2)} = \frac{z}{1-z^2-z}$$ and $$H(z) = (z+z^2) \frac{1}{1-(z+z^2)} = \frac{z+z^2}{1-z-z^2}$$ The conclusion is that $$G(z) = \frac{z}{1-z-z^2} \quad\text{and}\quad H(z) = \frac{z+z^2}{1-z-z^2}.$$

We recognise $G(z)$ as the generating function of the Fibonacci numbers so that $$g_n = F_n \quad\text{and}\quad h_n = F_n + F_{n-1} = F_{n+1}.$$ This concludes the proof that $g_n = h_{n-1}.$

Answer 2

Let $\mathcal{O}$ denote the class of all odd numbers, so that it has generating function $O(z) = z + z^3 + z^5 + \dots = \dfrac{z}{1-z^2}$. Then the class of compositions into odd parts is $$\mathcal{G} = \operatorname{S\scriptsize EQ}(\mathcal{O}) \implies G(z) = \frac{1}{1-O(z)} = \frac{1}{1-\frac{z}{1-z^2}} = \frac{1-z^2}{1-z-z^2}$$ where $G(z) = \sum_{n \ge 0} g(n) z^n$ is the generating function for $\mathcal{G}$.

Similarly, let $\mathcal{C}$ denote the class containing just the numbers $1$ and $2$ (so $C(z) = z+z^2$), then the class of compositions into parts equal to $1$ and $2$ is $$\mathcal{H} = \operatorname{S\scriptsize EQ}(\mathcal{C}) \implies H(z) = \frac{1}{1-C(z)} = \frac{1}{1-z-z^2}$$ where $H(z) = \sum_{n \ge 0} h(n) z^n$ is the generating function for $\mathcal{H}$.

Now you want to prove that $g(n) = h(n-1)$ for $n \ge 1$, or equivalently that $g(n+1) = h(n)$ for $n \ge 0$. We have $$\sum_{n \ge 0}g(n+1)z^n = \frac{G(z) - g(0)}{z} = \frac1z \left( \frac{1-z^2}{1-z-z^2} - 1\right) = \frac{1}{1-z-z^2} = H(z)$$ which proves the assertion.