I need to find the generating function of the sequence $c_n = (a_0, a_1, a_2, \ldots)$, where:
$$a_n =
\begin{cases}
2^{n/2} & \text{if $n$ is even,} \\
1 & \text{if $n$ is odd.}
\end{cases}$$
I have written out the first few terms of the sequence:
$$(1, 1, 2, 1, 4, 1, 8, 1, 16, 1, \ldots)$$ and have noticed that it seems to be a combination of the sequences $a_n = (1, 0, 2, 0, 4, 0, 8, 0, 16, 0, …)$ and $b_n = (0, 1, 0, 1, 0, 1, …).$
The first sequence, $a_n$, has the generating function
$$x\sum_{n = 0}^\infty(2x)^n = \frac{x}{1 – 2x}$$
and $b_n$ has the generating function
$$x\sum_{n = 0}^\infty x^{2n} = \frac{x}{1 – x^2}.$$
Therefore, I intuitively thought that $c_n = a_n + b_n$ and that the generating function of $c_n$ was equal to the sum of the generating functions of $a_n$ and $b_n$, which is equal to:
$$\frac{x}{1 – 2x} + \frac{x}{1 – x^2} = \frac{-x^3 – 2x^2 + 2x}{(1-2x)(1-x^2)}. \space\space (*)$$
However, when I tried to convert $(*)$ back to a form which involves an infinite sum, it did not give me the sequence that I expected ($c_n$).
I would appreciate help with the solution of this problem.
Best Answer
The problem is your first generating function. What you have typed is the generating function for the sequence $(0,1,2,4,8,16,...)$. The correct generating function is $$\sum_{n = 0}^\infty2^nx^{2n} = \frac{1}{1 - 2x^2}$$.
Once you have made this correction, your second step should work in producing the right generating function for the entire sequence.