Generating functions for compositions 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)$
 A: 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.
A: 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}.$
