GATE 2022 CS Q.36: solution and answer

GATE 2022 · CSQ.36 · 2 marks · MCQ

Which one of the following is the closed form for the generating function of the sequence ${a_{n}}_{n \geq 0}$ defined below?

a_{n} = {n + 1, 1, n is odd otherwise

(A)
$\frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
(B)
$\frac{x ( 3 - x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
(C)
$\frac{2 x}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
(D)
$\frac{x}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The closed form is $\frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$ , option (A).

Official answer: ASource: Official answer key, GATE 2022 CS (IIT Kharagpur)

Write $a_{n} = 1 + n [n odd]$ , so the sequence is $1, 2, 1, 4, 1, 6, \dots$ The all-ones part is $1$ for every $n \geq 0$ , and the extra part is $n$ at odd $n$ and $0$ at even $n$ .
The all-ones part has generating function $\sum_{n \geq 0} x^{n} = \frac{1}{1 - x}$ .
The extra part is $\sum_{n odd} n x^{n}$ . First, $\sum_{n odd} x^{n} = x + x^{3} + x^{5} + \dots = \frac{x}{1 - x ^{2}}$ .
Multiplying each coefficient by $n$ corresponds to the operator $x \frac{d}{d x}$ , so $\sum_{n odd} n x^{n} = x \frac{d}{d x} (\frac{x}{1 - x ^{2}})$ .
Differentiate: $\frac{d}{d x} \frac{x}{1 - x ^{2}} = \frac{( 1 - x ^{2} ) + 2 x ^{2}}{( 1 - x ^{2} ) ^{2}} = \frac{1 + x ^{2}}{( 1 - x ^{2} ) ^{2}}$ .
Hence the extra part is $\frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}}$ .
Add the two parts: $G (x) = \frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$ , which is option (A).
Check: $\frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} = x + 3 x^{3} + \dots$ , so the coefficient of $x^{1}$ is $1 + 1 = 2 = a_{1}$ and of $x^{3}$ is $3 + 1 = 4 = a_{3}$ . Option (B) would give $3 + 1 = 4$ at $x^{1}$ , which is wrong, and (C) and (D) give $2 + 1 = 3$ and $1 + 1 = 2$ at $x^{1}$ but fail at $x^{3}$ (coefficients $4 + 1 = 5$ and $2 + 1 = 3$ against $a_{3} = 4$ ).

KEY IDEA

Split the sequence into a constant part and an odd-index part. Get the odd-index part by applying $x \frac{d}{d x}$ to $\frac{x}{1 - x ^{2}}$ , the generating function of the odd powers.

WATCH OUT FOR

Forgetting that $n$ is a coefficient multiplier only on odd terms and using $\frac{x}{( 1 - x ^{2} ) ^{2}}$ or $\frac{2 x}{( 1 - x ^{2} ) ^{2}}$ . Also, differentiating $\frac{1}{1 - x ^{2}}$ and getting $\frac{2 x}{( 1 - x ^{2} ) ^{2}}$ is the series for $\sum 2 k x^{2 k}$ , which is not the extra part here.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 3 Recurrences questions, with notes