Which one of the following is the closed form for the generating function of the sequence {a_n}_{n>=0} defined below? a_n = { n+1, if n is odd { 1, otherwise A. (1+2x-x^2)/(1-x^2)^2 B. 1/(1-x)^2 C. (1+x)/(1-x)^2 D. x/(1-x^2)^2

GATE 2022 · Discrete Mathematics · Generating Functions · medium

Answer: G(x) = (1+2x-x^2)/(1-x^2)^2

1. Split by parity: Even part has a_n=1; odd part has a_n=n+1. The two sums are independent.
2. Close the even-index sum: Even sum = 1 + x^2 + x^4 + ... = 1/(1-x^2), valid for |x| < 1.
3. Close the odd-index sum: Odd sum = 2x + 4x^3 + 6x^5 + ... = 2x(1 + 2x^2 + 3x^4 + ...) = 2x * 1/(1-x^2)^2.
4. Combine over common denominator: Common denominator is (1-x^2)^2. G(x) = [(1-x^2) + 2x] / (1-x^2)^2 = (1+2x-x^2)/(1-x^2)^2.