# 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.

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.

• I will work on this suggestion. – Caleb Owusu-Yianoma May 21 '15 at 9:03
• I have managed to reach the correct solution. – Caleb Owusu-Yianoma May 21 '15 at 10:47

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

• Firstly, how do you arrive at the second equality in the second line of your answer? Secondly, I am not familiar with Cauchy products. – Caleb Owusu-Yianoma May 21 '15 at 9:27
• @CKKOY, the second equality in the second line comes from a change of variable $n$ to $n+1$. The Cauchy product just states that $\sum_na_nX^n\times \sum_nb_nX^n=\sum_n(\sum_{k=0}^na_kb_{n-k})X^n$, in what I have written $a_k=2^k$ and $b_k=1$. – Clément Guérin May 21 '15 at 10:04
• Sorry - I meant to ask you how you arrived at the second equality in the first line. – Caleb Owusu-Yianoma May 21 '15 at 10:50
• @CKKOY, it is just geometric summation : $1+2+...+2^{n-1}=\frac{2^n-1}{2-1}$. – Clément Guérin May 21 '15 at 15:58