6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

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

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

$\endgroup$
4
  • $\begingroup$ Firstly, how do you arrive at the second equality in the second line of your answer? Secondly, I am not familiar with Cauchy products. $\endgroup$ – Caleb Owusu-Yianoma May 21 '15 at 9:27
  • 1
    $\begingroup$ @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$. $\endgroup$ – Clément Guérin May 21 '15 at 10:04
  • $\begingroup$ Sorry - I meant to ask you how you arrived at the second equality in the first line. $\endgroup$ – Caleb Owusu-Yianoma May 21 '15 at 10:50
  • 1
    $\begingroup$ @CKKOY, it is just geometric summation : $1+2+...+2^{n-1}=\frac{2^n-1}{2-1}$. $\endgroup$ – Clément Guérin May 21 '15 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.