Find the generating function of this sequence

Question

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.

Answer 1

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.

Answer 2

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)} $$