GATE CS 2022 Q26 — Combinatorics: Counting, Recurrence Relations, Generating Functions

The given sequence is defined as:

$$a_n = \begin{cases} n+1, & \text{if } n \text{ is odd} \\ 1, & \text{otherwise} \end{cases}$$

Writing out the first few terms of the sequence $\{a_n\}_{n \ge 0}$:

$$a_0 = 1, \quad a_1 = 2, \quad a_2 = 1, \quad a_3 = 4, \quad a_4 = 1, \quad a_5 = 6, \dots$$

The generating function $A(x)$ for this sequence is:

$$A(x) = \sum_{n=0}^{\infty} a_n x^n = 1 + 2x + x^2 + 4x^3 + x^4 + 6x^5 + \dots$$

We can separate $A(x)$ into even and odd powers of $x$:

$$A(x) = (1 + x^2 + x^4 + \dots) + (2x + 4x^3 + 6x^5 + \dots)$$

The even part is a standard geometric series:

$$E(x) = 1 + x^2 + x^4 + \dots = \frac{1}{1-x^2}$$

The odd part can be simplified by factoring out $2x$:

$$O(x) = 2x(1 + 2x^2 + 3x^4 + 4x^6 + \dots)$$

Using the standard binomial series $\sum_{k=0}^{\infty} (k+1)y^k = \frac{1}{(1-y)^2}$ with $y = x^2$:

$$O(x) = \frac{2x}{(1-x^2)^2}$$

Combining both parts, we get:

$$A(x) = \frac{2x}{(1-x^2)^2} + \frac{1}{1-x^2} = \frac{2x + 1 - x^2}{(1-x^2)^2}$$

Now, let us simplify the expression in Option A to see if it matches:

$$\frac{x(1+x^2)}{(1-x^2)^2} + \frac{1}{1-x} = \frac{x+x^3}{(1-x^2)^2} + \frac{1+x}{1-x^2}$$ $$= \frac{x+x^3 + (1+x)(1-x^2)}{(1-x^2)^2}$$ $$= \frac{x+x^3 + 1 - x^2 + x - x^3}{(1-x^2)^2} = \frac{2x + 1 - x^2}{(1-x^2)^2}$$

Since both expressions are identical, Option A is the correct closed form.