<s>[INST] Find the generating function of this sequence 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.
 [/INST] Let us set $A(X)$ the generating function whose coefficients are $(a_n)$. I claim that :
$$A(X)-\frac{1}{1-X}=\sum_{n=1}^{\infty}(2^n-1)X^{2n}=\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}2^kX^{2n} $$
$$\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}2^kX^{2n}=X^2\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}2^kX^{2(n-1)}=X^2\sum_{n=0}^{\infty}\sum_{k=0}^{n}2^kX^{2n} $$
Now the last generating function appears as a Cauchy product in the variable $Y:=X^2$ so :
$$X^2\sum_{n=0}^{\infty}\sum_{k=0}^{n}2^kX^{2n}=X^2\sum_{n=0}^{\infty}2^nX^{2n}\sum_{n=0}^{\infty}X^{2n}=X^2\frac{1}{1-X^2}\frac{1}{1-2X^2}$$
Now :
$$A(X)=\frac{1}{1-X}+\frac{X^2}{(1-X^2)(1-2X^2)}=\frac{(1+X)(1-2X^2)+X^2}{(1-X^2)(1-2X^2)} $$
$$A(X)=\frac{1+X-2X^2-2X^3+X^2}{(1-X^2)(1-2X^2)}=\frac{1+X-X^2-2X^3}{(1-X^2)(1-2X^2)}  $$
</s>