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$

2 Answers 2

Reset to default
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$ Commented May 21, 2015 at 9:03
  • $\begingroup$ I have managed to reach the correct solution. $\endgroup$ Commented May 21, 2015 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$ Commented May 21, 2015 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$ Commented May 21, 2015 at 10:04
  • $\begingroup$ Sorry - I meant to ask you how you arrived at the second equality in the first line. $\endgroup$ Commented May 21, 2015 at 10:50
  • 1
    $\begingroup$ @CKKOY, it is just geometric summation : $1+2+...+2^{n-1}=\frac{2^n-1}{2-1}$. $\endgroup$ Commented May 21, 2015 at 15:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.