If the ordinary generating function of sequence {a_n}_{n=0}^{infinity} is (1+z)/(1-z)^3, then a_2 - a_1 is equal to ___.

GATE 2017 · Discrete Mathematics · Generating Functions · medium

Answer: 5

1. Split G(z) into two recognizable series: G(z) = (1+z)/(1-z)^3 = 1/(1-z)^3 + z/(1-z)^3. With k=3: 1/(1-z)^3 = sum_{n>=0} C(n+2,2) z^n.
2. Compute a_1 from both parts: [z^1] 1/(1-z)^3 = C(3,2) = 3. [z^1] z/(1-z)^3 = [z^0] 1/(1-z)^3 = C(2,2) = 1. So a_1 = 3 + 1 = 4.
3. Compute a_2 from both parts: [z^2] 1/(1-z)^3 = C(4,2) = 6. [z^2] z/(1-z)^3 = [z^1] 1/(1-z)^3 = C(3,2) = 3. So a_2 = 6 + 3 = 9.
4. Compute the difference: a_2 - a_1 = 9 - 4 = 5. Wait — let us recheck: the shift gives [z^n] z/(1-z)^3 = C((n-1)+2, 2) = C(n+1,2) for n>=1. So for n=1: C(2,2)=1. For n=2: C(3,2)=3. Then a_1 = 3+1=4, a_2 = 6+3=9, difference = 5. But the standard answer reported for this question is 6. Let us use direct expansion: G(z) = (1+z)(1-z)^{-3}. (1-z)^{-3} = 1 + 3z + 6z^2 + 10z^3 + ... So G(z) = (1+z)(1 + 3z + 6z^2 + ...) = 1 + 3z + 6z^2 + ... + z + 3z^2 + ... = 1 + 4z + 9z^2 + .... Thus a_1=4, a_2=9, and a_2 - a_1 = 5.