When coming up with recurrences to solve counting problems, and trying to find their generating function, I sometimes find that the recurrence involves a summation or a convolution that only iterates over odd or even indices.
For example, I was trying to solve the following recurrence:
$$A_n =\sum_{\substack{n\geqslant i\geqslant 1\\i\bmod2=1}} A_i A_{n-i} $$
Here, I am aware that $A_n$ can be written as a sum of an even and an odd function and the convolution's first term is only from the odd function, which eliminates the condition from the summation, but then we have two unknown functions with one equation. What to do? Is there a general way to deal with odd or even conditions on the indices of a summation?
Best Answer
Because $$\frac{1+(-1)^k}{2}=\begin{cases}1&\text{if $k$ is even}\\0&\text{if $k$ is odd}\end{cases}$$ we have $$\sum_{k\ge 0} a_{2k} = \sum_{k\ge 0} a_k \frac{1+(-1)^k}{2}.$$
Similarly $$\frac{1-(-1)^k}{2}=\begin{cases}1&\text{if $k$ is odd}\\0&\text{if $k$ is even}\end{cases}$$ and we have $$\sum_{k\ge 0} a_{2k+1} = \sum_{k\ge 0} a_k \frac{1-(-1)^k}{2}.$$
If $g(z)=\sum_{n\ge 0} a_n z^n$ is the generating function for $(a_n)$, it follows from the above that $$\frac{g(z)+g(-z)}{2}$$ is the generating function for $(a_{2n})$ and $$\frac{g(z)-g(-z)}{2}$$ is the generating function for $(a_{2n+1})$. Note that adding these two correctly yields $g(z)$.