Interestingly restricted compositions of $n$ Let $n$ be a non-negative integer. How many compositions of $n$ are there where the $i$-th part has the same parity as $i$?
The main problem I'm having with this problem is that I can't really formulate a single generating function for the set of all tuples of natural numbers where the $i$-th element has the same parity as $i$. How should I proceed?

Let $a_n$ be the number of compositions of $n$ whose $i$-the part has the same parity as $i$, and let $b_n$ be the number of compositions of $n$ whose $i$-the part has the opposite parity to $i$. Considering the possible values of the first part of a composition of $n$, we see that
$$a_{2n+1}=\sum_{k=0}^nb_{2k}\quad\text{ and }\quad a_{2n}=\sum_{k=0}^{n-1}b_{2k+1}$$
and
$$b_{2n+1}=\sum_{k=0}^{n-1}a_{2k+1}\quad\text{ and }\quad b_{2n}=\sum_{k=0}^{n-1}a_{2k}\;,$$
and hence that 
$$\left\{\begin{align*}a_n&=a_{n-2}+b_{n-1}\\
b_n&=a_{n-2}+b_{n-2}\;.
\end{align*}\right.\tag{1}$$
If we make the blanket assumption that $a_n=b_n=0$ for all $n<0$ and set $a_0=0$ and $b_0=1$, $(1)$ is valid for all $n\in\Bbb Z$ except in the case of $b_0$, adding an Iverson bracket term to get
$$\left\{\begin{align*}a_n&=a_{n-2}+b_{n-1}\\
b_n&=a_{n-2}+b_{n-2}+[n=0]\;.
\end{align*}\right.\tag{2}$$
fixes this.
Let
$$A(x)=\sum_{n\ge 0}a_nx^n\quad\text{and}\quad B(x)=\sum_{n\ge 0}b_nx^n$$
be the generating functions for the two sequences. Then multiplying the recurrences $(2)$ by $x^n$ and summing over $n\ge 0$ yields 
$$\left\{\begin{align*}
A(x)&=x^2A(x)+xB(x)\\
B(x)&=x^2A(x)+x^2B(x)+1\;.
\end{align*}\right.$$
Then
$$B(x)=\frac{x^2}{1-x^2}A(x)+\frac1{1-x^2}$$
and
$$A(x)=\frac{x}{1-x^2}B(x)=\frac{x^3}{(1-x^2)^2}A(x)+\frac{x}{(1-x^2)^2}\;,$$
so
$$\begin{align*}
A(x)&=\frac{x}{1-x^2}\left(1-\frac{x^3}{(1-x^2)^2}\right)^{-1}\\\\
&=\frac{x}{1-x^2}\cdot\frac{(1-x^2)^2}{1-2x^2-x^3+x^4}\\\\
&=\frac{x(1-x)}{1-2x^2-x^3+x^4}
\end{align*}$$
and
$$\begin{align*}
B(x)&=\frac{1-x^2}xA(x)\\\\
&=\frac{(1-x)^2(1+x)}{1-2x^2-x^3+x^4}\;.
\end{align*}$$
Some actual numbers:
$$\begin{array}{rccc}
n:&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\
a_n:&0&1&0&2&1&3&4&5&10&11&21&27&43&64\\
b_n:&1&0&1&1&1&3&2&6&6&11&16&22&37&43
\end{array}$$
OEIS has $\langle a_n+b_n:n\ge 0\rangle=\langle b_{n+2}:n\ge 0\rangle$ as OEIS A062200 and $\langle a_n:n\ge 0\rangle$ as OEIS A122514. It has little more information beyond the recurrence
$$b_n=2b_{n-2}+b_{n-3}-b_{n-4}\;,$$
which is easily derived from $(1)$.
