Which one of the following is the closed form for the generating function of…
2022
Which one of the following is the closed form for the generating function of the sequence {an}n ≥ 0 defined below?
\(a(n) = \begin{cases}
n + 1, & \text n \text{ is odd}, \\
1, & \text{otherwise}.
\end{cases}
\)
- A.
\(\frac {x(1 + x^2)} {(1 - x^2)^2} + \frac {1} {1 - x}\) - B.
\(\frac {x(3 - x^2)} {(1 - x^2)^2} + \frac {1} {1 - x}\) - C.
\(\frac {2x} {(1 - x^2)^2} + \frac {1} {1 - x}\) - D.
\(\frac {x} {(1 - x^2)^2} + \frac {1} {1 - x}\)
Attempted by 31 students.
Show answer & explanation
Correct answer: A
Key idea: separate the constant 1 from the odd-index contributions.
Write the sequence as a(n)=1 for every n, plus an extra n when n is odd. Thus
G(x)=sum_{n>=0} a(n)x^n = sum_{n>=0}1*x^n + sum_{odd n} n x^n = 1/(1-x) + sum_{k>=0} (2k+1) x^{2k+1}.
Evaluate the odd-index sum: sum_{k>=0}(2k+1)x^{2k+1} = x*(2*sum_{k>=0} k (x^2)^k + sum_{k>=0} (x^2)^k).
Use standard sums: sum_{k>=0} (x^2)^k = 1/(1-x^2) and sum_{k>=0} k (x^2)^k = x^2/(1-x^2)^2, so the odd sum equals x*(2*x^2/(1-x^2)^2 + 1/(1-x^2)) = x(1+x^2)/(1-x^2)^2.
Therefore the generating function is
G(x) = x(1+x^2)/(1-x^2)^2 + 1/(1-x).
Quick check: expanding the series gives coefficients 1,2,1,4,1,6,... which match a0,a1,a2,a3,a4,a5 respectively.