The GATE Grind

GATE 2018 CS – Question 11

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

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

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\dfrac{3-x}{(1-x)^2}$

Explanation

The ordinary generating function is $A(x)=\sum_{n=0}^\infty(2n+3)x^n$.

Start with $\sum_{n\ge0}x^n=1/(1-x)$. Differentiating and multiplying by $x$ gives $\sum_{n\ge0}nx^n=x/(1-x)^2$.

Hence
$$A(x)=\frac{2x}{(1-x)^2}+\frac3{1-x}=\frac{3-x}{(1-x)^2}.$$
The answer is **D**. These identities also hold as formal power-series identities.

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

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