TAOCP 1.2.9 Exercise 26
Let G(z)=\sum_{n\ge 0} a_n z^n.
Section 1.2.9: Generating Functions
Exercise 26. [M40] Explore a generalization of the notation (31) according to which we might write, for example, $[z^2 - 2z^5]G(z)=a_2-2a_5$ when $G(z)$ is given by (1).
Verified: yes
Solve time: 42s
Setup
Let
$$ G(z)=\sum_{n\ge 0} a_n z^n. $$
For each nonnegative integer $k$, the coefficient extraction operator satisfies
$$ [z^k]G(z)=a_k. $$
Let $P(z)=\sum_{k=0}^m c_k z^k$ be a polynomial. The expression to be defined is of the form
$$ [P(z)]G(z), $$
with the example requirement
$$ [z^2-2z^5]G(z)=a_2-2a_5. $$
The goal is to give a consistent extension of coefficient extraction to linear combinations of powers of $z$ and to justify the resulting identity.
Solution
Define the operation on polynomials $P(z)=\sum_{k=0}^m c_k z^k$ by
$$ [P(z)]G(z)=\sum_{k=0}^m c_k [z^k]G(z). $$
Substituting $G(z)=\sum_{n\ge 0} a_n z^n$ gives $[z^k]G(z)=a_k$ for each $k\ge 0$. Hence
$$ [P(z)]G(z)=\sum_{k=0}^m c_k a_k. $$
For the specific polynomial $P(z)=z^2-2z^5$, the coefficients are $c_2=1$, $c_5=-2$, and all other $c_k=0$. Applying the definition yields
$$ [z^2-2z^5]G(z)=1\cdot a_2+(-2)\cdot a_5=a_2-2a_5. $$
Linearity follows directly from the definition: if $P(z)$ and $Q(z)$ are polynomials and $\alpha,\beta$ are scalars, then
$$ [\alpha P(z)+\beta Q(z)]G(z) =\sum_k (\alpha p_k+\beta q_k)a_k =\alpha \sum_k p_k a_k+\beta \sum_k q_k a_k =\alpha [P(z)]G(z)+\beta [Q(z)]G(z). $$
This defines a linear functional on the polynomial ring in $z$ acting on the coefficient sequence of $G(z)$.
Verification
For each $k\ge 0$, the identity $[z^k]G(z)=a_k$ follows directly from the defining expansion of $G(z)$ and uniqueness of coefficients in formal power series.
Applying the definition of $[P(z)]G(z)$ to a monomial $P(z)=z^k$ gives $[z^k]G(z)=a_k$, matching the required behavior.
For $P(z)=z^2-2z^5$, substitution into the linear combination formula produces exactly $a_2-2a_5$, with no additional terms since all other coefficients of $P(z)$ are zero.