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)$

  • 2
    $\begingroup$ Hello! Please provide us with a bit of information about what you've tried and where you're getting stuck. Do that, and it will be much easier for us to figure out how to best help you. $\endgroup$ – Nick Peterson Apr 3 '14 at 11:26
  • $\begingroup$ @NicholasR.Peterson I have no idea about this one :( Would appreciate anything to get me started. $\endgroup$ – Dave Apr 3 '14 at 12:32
  • $\begingroup$ Can you write down the generating functions for the case when there are no restrictions on the compositions? $\endgroup$ – ShreevatsaR Apr 4 '14 at 4:05

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}.$

  • $\begingroup$ +1. But note that: (A) your generating function $\frac{z}{1-z-z^2}=z+z^2+2z^3+\dots$. But arguably it makes sense to say $g(0)=1$ (for the empty composition), which gives the GF $\frac{z}{1-z-z^2}+1=\frac{1-z^2}{1-z-z^2}$ as in my answer. Similarly, $\frac{z+z^2}{1-z-z^2}=z+2z^2+3z^3+\dots$, and adding $h(0)=1$ gives $\frac{z+z^2}{1-z-z^2}+1=\frac{1}{1-z-z^2}$. Allowing the zero values lets us say that $g(n)=h(n-1)$ for $n\ge1$ instead of only $n\ge2$. (B) We can argue directly from GFs instead of using facts about Fibonacci numbers: in your notation, we have $zH(z)=G(z)+z$, which proves it. $\endgroup$ – ShreevatsaR Apr 6 '14 at 5:57

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.

  • $\begingroup$ We can also prove $g(n) = h(n-1)$ for $n \ge 1$ by noticing that $$\sum_{n \ge 1}h(n-1)z^n = zH(z) = \frac{z}{1-z-z^2}=\frac{1-z^2-(1-z-z^2)}{1-z-z^2} = G(z) - 1 = \sum_{n\ge 1}g(n)z^n$$ $\endgroup$ – ShreevatsaR Apr 6 '14 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.