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

$\frac{x(1+x^2)}{(1-x^2)^2}+\frac{1}{1-x}$
$\frac{x(3-x^2)}{(1-x^2)^2}+\frac{1}{1-x}$
$\frac{2x}{(1-x^2)^2}+\frac{1}{1-x}$
$\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

Write $a_n=1+n$ for odd $n$ and 1 for even $n$, so $G=\frac{1}{1-x}+\sum_{n\text{ odd}}nx^n$. Since $\sum_{n\text{ odd}}x^n=\frac{x}{1-x^2}$, applying $x\,\frac{d}{dx}$ gives $\frac{x(1+x^2)}{(1-x^2)^2}$.