GATE CS 2005 Q50 — Combinatorics: Counting, Recurrence Relations, Generating Functions

We are given the generating function:

$$G(x) = \frac{1}{(1-x)^2} = \sum_{i=0}^\infty g(i)x^i$$

We can find the coefficients $g(i)$ using the standard infinite geometric series expansion for $|x| < 1$:

$$\frac{1}{1-x} = \sum_{i=0}^\infty x^i = 1 + x + x^2 + x^3 + \dots$$

Differentiating both sides with respect to $x$ gives:

$$\frac{d}{dx}\left(\frac{1}{1-x}\right) = \frac{d}{dx}\left(\sum_{i=0}^\infty x^i\right)$$

$$\frac{1}{(1-x)^2} = \sum_{i=1}^\infty i x^{i-1}$$

To write this in the form $\sum_{i=0}^\infty g(i)x^i$, we shift the summation index by setting $j = i - 1$ (which means $i = j + 1$):

$$\frac{1}{(1-x)^2} = \sum_{j=0}^\infty (j+1) x^j$$

Replacing the dummy variable $j$ back with $i$, we get:

$$G(x) = \sum_{i=0}^\infty (i+1) x^i$$

Comparing this with the given definition $G(x) = \sum_{i=0}^\infty g(i)x^i$, we find:

$$g(i) = i + 1$$

Thus, the correct option is B.