TAOCP 5.1.3 Exercise 26
Let \(\vartheta = z \frac{d}{dz}\).
Exercise 26. [M20] Let $\vartheta$ be the operation $z \frac{d}{dz}$, which multiplies the coefficient of $z^n$ in a generating function by $n$. Show that the result of applying $\vartheta$ to $1/(1-z)$ repeatedly, $m$ times, can be expressed in terms of Eulerian numbers.
Verified: yes
Solve time: 18m35s
Solution
Let (\vartheta = z \frac{d}{dz}). For any formal power series (f(z) = \sum_{n\ge 0} a_n z^n) we have (\vartheta f(z) = \sum_{n\ge 0} n a_n z^n); hence (\vartheta^m f(z) = \sum_{n\ge 0} n^m a_n z^n). Applying this to the geometric series [ \frac{1}{1-z} = \sum_{n\ge 0} z^n, ] we obtain [ \vartheta^m \frac{1}{1-z} = \sum_{n\ge 0} n^m z^n \qquad (m \ge 0). ]
The Eulerian numbers (\left\langle {n \atop k} \right\rangle) are defined by the recurrence [ \left\langle {n \atop k} \right\rangle = (k+1)\left\langle {n-1 \atop k} \right\rangle + (n-k)\left\langle {n-1 \atop k-1} \right\rangle \qquad (n>0), ] with boundary conditions (\left\langle {0 \atop k} \right\rangle = \delta_{k0}). Table 1 in the text gives their values for small (n).
We claim that for (m \ge 1) [ \vartheta^m \frac{1}{1-z} = \frac{z}{(1-z)^{m+1}}, A_m(z), \tag{*} ] where (A_m(z)) is the Eulerian polynomial [ A_m(z) = \sum_{k=0}^{m-1} \left\langle {m \atop k} \right\rangle z^k. ] Equivalently, because (\left\langle {m \atop m} \right\rangle = 0), [ \vartheta^m \frac{1}{1-z} = \sum_{k=0}^{m} \left\langle {m \atop k} \right\rangle \frac{z^{k+1}}{(1-z)^{m+1}}. ]
Proof by induction on (m).
Base case (m=1). (\left\langle {1 \atop 0} \right\rangle = 1), so (A_1(z)=1). The right‑hand side of ((*)) is (z/(1-z)^2). Direct differentiation gives (\vartheta(1/(1-z)) = z/(1-z)^2). Hence the formula holds for (m=1).
Inductive step. Assume ((*)) holds for some (m \ge 1). Then [ \vartheta^{m+1} \frac{1}{1-z} = \vartheta \left( \frac{z A_m(z)}{(1-z)^{m+1}} \right) = z \frac{d}{dz} \left( \frac{z A_m(z)}{(1-z)^{m+1}} \right). ] Let (N(z) = z A_m(z)) and (D(z) = (1-z)^{m+1}). Using the quotient rule, [ \frac{d}{dz} \frac{N}{D} = \frac{N'D^{-2}\bigl( N' D - N D' \bigr) = \frac{ (A_m + z A_m')(1-z)^{m+1} + (m+1) z A_m (1-z)^m }{ (1-z)^{2m+2} }. ] Multiplying by (z) yields [ \vartheta^{m+1} \frac{1}{1-z} = \frac{z \bigl[ (A_m + z A_m')(1-z) + (m+1) z A_m \bigr] }{ (1-z)^{m+2} }. ] We must show that the numerator equals (z A_{m+1}(z)), i.e. that [ A_{m+1}(z) = (A_m + z A_m')(1-z) + (m+1) z A_m. \tag{1} ] Write (A_m(z) = \sum_{k=0}^{m-1} a_k z^k) with (a_k = \left\langle {m \atop k} \right\rangle). Then [ \begin{aligned} (A_m + z A_m')(1-z) + (m+1) z A_m &= \sum_{k=0}^{m-1} a_k z^k
- \sum_{k=1}^{m-1} k a_k z^k
- \sum_{k=1}^{m-1} a_k z^{k+1}
- \sum_{k=1}^{m-1} k a_k z^{k+1}
- \sum_{k=0}^{m-1} (m+1) a_k z^{k+1}. \end{aligned} ] Collecting the coefficient of (z^k) for (0 \le k \le m) (with (a_m = 0)): [ \begin{aligned} k=0 &: \quad a_0, \ 1 \le k \le m-1 &: \quad a_k + k a_k - a_{k-1} - (k-1) a_{k-1} + (m+1) a_{k-1} = (k+1) a_k + (m+1-k) a_{k-1}, \ k=m &: \quad -a_{m-1} - (m-1) a_{m-1} + (m+1) a_{m-1} = a_{m-1}. \end{aligned} ] The right‑hand side of (1) therefore equals [ \sum_{k=0}^{m} \bigl[ (k+1) a_k + (m+1-k) a_{k-1} \bigr] z^k \qquad (a_{-1}=a_m=0). ] By the recurrence (2) for Eulerian numbers, [ \left\langle {m+1 \atop k} \right\rangle = (k+1)\left\langle {m \atop k} \right\rangle + (m+1-k)\left\langle {m \atop k-1} \right\rangle, ] this is exactly (\sum_{k=0}^{m} \left\langle {m+1 \atop k} \right\rangle z^k = A_{m+1}(z)). Thus (1) holds, completing the induction.
For (m=0) the operator (\vartheta^0) is the identity, and the formula gives simply (1/(1-z)); the expression in terms of Eulerian numbers is not needed for this trivial case.
[ \boxed{\vartheta^m \frac{1}{1-z} = \frac{z}{(1-z)^{m+1}} \sum_{k=0}^{m-1} \left\langle {m \atop k} \right\rangle z^k \qquad (m \ge 1)} ]
This completes the proof. ∎