The GATE Grind

GATE 2022 CS – Question 36

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 2 marks · Multiple choice

Which one of the following is the closed form for the generating function of the sequence $\{a_n\}_{n\ge0}$ defined below?
$a_n=\begin{cases}n+1, & n \text{ is odd}\\ 1, & \text{otherwise}\end{cases}$

  1. $\frac{x(1+x^2)}{(1-x^2)^2}+\frac{1}{1-x}$
  2. $\frac{x(3-x^2)}{(1-x^2)^2}+\frac{1}{1-x}$
  3. $\frac{2x}{(1-x^2)^2}+\frac{1}{1-x}$
  4. $\frac{x}{(1-x^2)^2}+\frac{1}{1-x}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\frac{x(1+x^2)}{(1-x^2)^2}+\frac{1}{1-x}$

Explanation

$a_n=1$ for even $n$ and $a_n=n+1$ for odd $n$, so $a_n=1+n\cdot[n\text{ odd}]$.

$$G(x)=\sum_{n\ge0}a_nx^n=\underbrace{\sum_{n\ge0}x^n}_{1/(1-x)}+\sum_{n\text{ odd}}nx^n.$$

Let $O(x)=\sum_{n\text{ odd}}x^n=\dfrac x{1-x^2}$. Then $\sum_{n\text{ odd}}nx^n=x\,O'(x)$:
$$O'(x)=\frac{(1-x^2)+2x^2}{(1-x^2)^2}=\frac{1+x^2}{(1-x^2)^2},\qquad xO'(x)=\frac{x(1+x^2)}{(1-x^2)^2}.$$

$$G(x)=\frac{x(1+x^2)}{(1-x^2)^2}+\frac1{1-x}:\text{ option (A)}.$$

More Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions

All Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions →