GATE CS 2018 Q1 — Combinatorics: Counting, Recurrence Relations, Generating Functions

The generating function $A(x)$ for the sequence $\{a_n\}$ is defined as:

Given that $a_n = 2n + 3$ for $n \ge 0$, we can split the summation into two parts:

We use the following standard closed-form generating functions:

1. The sum of an infinite geometric series: $$\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$$
2. Differentiating both sides with respect to $x$ and multiplying by $x$: $$\sum_{n=0}^{\infty} n x^n = \frac{x}{(1-x)^2}$$

Substituting these standard forms back into our expression for $A(x)$:

To combine the terms, find a common denominator of $(1-x)^2$:

Thus, the closed-form expression is $\frac{3-x}{(1-x)^2}$, which corresponds to option D.