How many compositions of n are there in which each part is an even number? I need to find out how many compositions of n there are in which each part is an even number.
I think I have the correct generating function by doing the following:
$$S = ∪_{k\geq0}N_{even}^k$$
where $k=0$ is the empty composition and $N_{even}=\{2,4,6,...\}$ so,
$$\Phi_S(x) = \Phi_{∪_{k\geq0}N_{even}^k}(x)$$
$$\Phi_S(x) = \sum\limits_{k\geq0}^{} \Phi_{N_{even}^k}(x)$$
$$\Phi_S(x) = \sum\limits_{k\geq0}^{} (\sum\limits_{i\geq0}^{}x^{2i+2})^k$$
$$\Phi_S(x) = \sum\limits_{k\geq0}^{} (x^2(1-x^2)^{-1})^k$$
$$\Phi_S(x) = \dfrac{1}{1-(x^2(1-x^2)^{-1})}$$
$$\Phi_S(x) = \dfrac{1-x^2}{1-2x^2}$$
and the number of compositions would be
$$[x^n](\dfrac{1-x^2}{1-2x^2})$$
Simplifying this to find the number of compositions is where I get stuck. Any help would be appreciated!
 A: How about finding the number of compositions of $\frac n2$ and then doubling all the parts?  Since there are $2^{\frac n2-1}$ of them, that is the number of compositions of $n$ into even parts.
A: Your derivation has a small but essential flaw: you are allowing $0$ as part of compositions, but then the total number of partitions of a given number becomes infinite (as one can add in zero parts without limit), and the generating series method cannot help you out (but it does tell you that something is wrong).
Compositions of $n$ (with parts of nonzero size) can easily be counted by a direct combinatorial argument, but the generating series approach does work fine for it. Let $C=\sum_ic_iX^i$ be the generating series for the possible "values" of a single item (i.e., there are $c_i$ possible items of values $i$), then provided $c_i=0$ (there must be no items contributing no value at all, for the reasons indicated above), there is a generating series for the number of strings (implying that order is relevant) of $0$ or more items by total value, and it is given by $\sum_{i\geq0}C^i=\frac1{1-C}$ (note that the constant coefficient of the denominator is$~1$ so that division as formal poser series is possible). Now for counting compositions, one wants $c_i=1$ whenever $i>0$, so $C=X+X^2+\cdots=\frac X{1-X}$, and $\frac1{1-C}=\frac{1-X}{1-2X}$. The coefficients $m_i$ of this series satisfy the recurrence $m_i=2m_{i-1}$ for $i\geq2$ with initial values $1=m_0=m_1$, so that they are given explicitly by
$$
  m_i=\begin{cases} 1&\text{if }i=0\\2^{i-1}&\text{if }i>0,\end{cases}
$$
which agrees with what is found by a direct combinatorial argument.
For counting compositions into even parts, just change to $C=X^2+X^4+X^6\cdots=\frac{X^2}{1-X^2}$, which effectively replaces $X$ by $X^2$ throughout, given generating series
$$
  \frac{1-X^2}{1-2X^2}=\sum_{i\geq0}m_iX^{2i},
$$
with the same $m_i$ as above. In other words the number of such compositions of $n$ is $0$ for odd$~n$, it is $1$ for $n=0$, and it is $2^{n/2-1}$ for even$~n>0$.
A: The best approach, as suggested by Ross Millikan, is to observe that any composition of $n$ into even parts (say) $2a_1 + 2a_2 + \dots + 2a_k = n$ corresponds uniquely to a composition of $n/2$ into parts $a_1 + a_2 + \dots + a_k = n/2$, so the answer you seek is the number of compositions of $n/2$.
However, if you want to do it via generating functions, your generating function is correct.
Just to re-derive it: you could say (with $\mathcal{C}_{\text{e}}$ denoting the class of compositions into even parts):
$$\mathcal{C}_{\text{e}} = \operatorname{S\scriptsize EQ}(\mathcal{E})$$
$$C_{\text{e}}(z) = \frac{1}{1-E(z)}$$
where $\mathcal{E}$ denotes the class of positive even integers, with generating function $E(z)$.
$$\mathcal{E} = \operatorname{S\scriptsize EQ}_{\ge 1}(\mathcal{Z} \times \mathcal{Z})$$
$$E(z) = \frac{z^2}{1-z^2} = z^2 + z^4 + z^6 + \dots.$$
So the generating function you want is (as you got):
$$C_{\text{e}}(z) = \frac{1}{1-\frac{z^2}{1-z^2}} = \frac{1-z^2}{1-2z^2}$$
And the number you seek is
$$[z^n]C_{\text{e}}(z) = [z^n]\frac{1-z^2}{1-2z^2} = [y^{n/2}]\frac{1-y}{1-2y}$$
with the substitution $y = z^2$, if you notice that only $z^2$ terms exist (this observation, that $C_{\text{e}}(z) = C(z^2)$ where $C$ is the generating function for compositions, is essentially the same as the bijection between even compositinos of $n$ and all compositions of $n/2$).
But even if you don't notice this,
$$\begin{align}
[z^n]\frac{1-z^2}{1-2z^2} 
&= [z^n]\frac{1}{1-2z^2} - [z^n]\frac{z^2}{1-2z^2} \\
&= [z^n]\left(\sum_{k\ge0} (2z^2)^k\right) - [z^{n-2}]\left(\sum_{k\ge0} (2z^2)^k\right) \\
&= 2^{n/2} - 2^{(n-2)/2}\\
&= 2^{n/2 - 1}
\end{align}$$
(I'm afraid you do have to notice some connection between $n$ and $n/2$ eventually, since it turns up the answer! But this may be easier for you to notice, when you're explicitly looking at coefficients.)
