GATE 2018 CS Q.1: solution and answer

GATE 2018 · CSQ.1 · 1 mark · MCQ

Which one of the following is a closed form expression for the generating function of the sequence ${a_{n}}$ , where $a_{n} = 2 n + 3$ for all $n = 0, 1, 2, \dots$ ?

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The generating function is $\frac{3 - x}{( 1 - x ) ^{2}}$ , which is option (D).

Official answer: DSource: Official answer key, GATE 2018 CS (IIT Guwahati)

The generating function is $G (x) = \sum_{n \geq 0} (2 n + 3) x^{n}$ . Split it into $2 \sum_{n \geq 0} n x^{n} + 3 \sum_{n \geq 0} x^{n}$ .
Geometric series: $\sum_{n \geq 0} x^{n} = \frac{1}{1 - x}$ for $∣ x ∣ < 1$ , so the constant part gives $\frac{3}{1 - x}$ .
Differentiate the geometric series: $\sum_{n \geq 1} n x^{n - 1} = \frac{1}{( 1 - x ) ^{2}}$ . Multiply by $x$ : $\sum_{n \geq 0} n x^{n} = \frac{x}{( 1 - x ) ^{2}}$ . So the $2 n$ part gives $\frac{2 x}{( 1 - x ) ^{2}}$ .
Add over the common denominator: $G (x) = \frac{2 x}{( 1 - x ) ^{2}} + \frac{3 ( 1 - x )}{( 1 - x ) ^{2}} = \frac{2 x + 3 - 3 x}{( 1 - x ) ^{2}} = \frac{3 - x}{( 1 - x ) ^{2}} .$
Check with the first two terms: $a_{0} = 3$ and $a_{1} = 5$ . Since $\frac{1}{( 1 - x ) ^{2}} = 1 + 2 x + 3 x^{2} + \dots$ , we get $(3 - x) (1 + 2 x + 3 x^{2} + \dots) = 3 + 6 x - x + \dots = 3 + 5 x + \dots$ , which matches. The answer is option (D).

KEY IDEA

Write $2 n + 3$ as a combination of $n$ and $1$ . The generating function of $1$ is $\frac{1}{1 - x}$ , and applying $x \frac{d}{d x}$ to it gives the generating function of $n$ , which is $\frac{x}{( 1 - x ) ^{2}}$ . Then combine over $(1 - x)^{2}$ .

WATCH OUT FOR

Forgetting the factor $x$ in $\sum n x^{n} = \frac{x}{( 1 - x ) ^{2}}$ , or forgetting to rewrite $\frac{3}{1 - x}$ as $\frac{3 ( 1 - x )}{( 1 - x ) ^{2}}$ before adding. Checking the first two coefficients ( $3$ and $5$ ) catches both slips.

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

GATE 2018 CS Q.1: solution and answer

Answer and solution

More Recurrences questions