TAOCP 7.2.1.5 Exercise 56

We work with the notation of Section 7.

taocpmathematicsalgorithmsvolume-4hm-hard

Section 7.2.1.5: Generating All Set Partitions

Exercise 56. ▶ [HM26] Let $g(z)=\alpha^{-1}\ln(e^z-1)-\ln z$ and $\sigma=\alpha-\beta$ as in (37).

a) Prove that $(-\sigma)^{n+1}g^{(n+1)}(\sigma)=n!-\sum_{k=0}^n \left\langle\begin{array}{c} n \ k \end{array}\right\rangle \alpha^k\beta^{n-k}$, where the Eulerian numbers $\left\langle\begin{array}{c} n \ k \end{array}\right\rangle$ are defined in Section 5.1.3.

b) Prove that $\dfrac{\beta}{\alpha}n!<\sum_{k=0}^n \left\langle\begin{array}{c} n \ k \end{array}\right\rangle \alpha^k\beta^{n-k}<n!$ for all $\sigma>0$. Hint: See exercise 5.1.3–25.

c) Now verify the inequality (42).

Verified: no
Solve time: 15m56s

Setup

We work with the notation of Section 7.2.1.5. The constants (\alpha,\beta,\sigma) are defined by (37) and (40); from Exercise 54 we have [ s=\frac{\sigma}{2},\qquad \frac{\alpha+\beta}{2}=s\coth s,\qquad \sqrt{\alpha\beta}=s\csch s. ] Solving these gives [ \alpha=\frac{\sigma}{1-e^{-\sigma}},\qquad \beta=\frac{\sigma e^{-\sigma}}{1-e^{-\sigma}}, ] which satisfy [ \alpha-\beta=\sigma,\qquad e^{\sigma}=\frac{\alpha}{\beta},\qquad \frac{\beta}{\alpha}=e^{-\sigma}. ] The function (g) is [ g(z)=\alpha^{-1}\ln(e^z-1)-\ln z. ] Eulerian numbers (\left\langle{n\atop k}\right\rangle) are defined in Section 5.1.3; they obey the symmetry (\left\langle{n\atop k}\right\rangle=\left\langle{n\atop n-1-k}\right\rangle) and the generating function [ \sum_{m=1}^{\infty}m^n y^m = \frac{y,A_n(y)}{(1-y)^{n+1}},\qquad A_n(y)=\sum_{k=0}^{n-1}\left\langle{n\atop k}\right\rangle y^k ] (with (A_0(y)=1)). All sums involving Eulerian numbers are understood to have (\left\langle{n\atop n}\right\rangle=0).

Solution

a)

Let (t=z-\sigma). Using (e^{\sigma}=\alpha/\beta) we rewrite [ e^{\sigma+t}-1 = \frac{\alpha}{\beta}e^t-1 = \frac{\alpha e^t-\beta}{\beta} = \frac{\alpha(e^t-e^{-\sigma})}{\beta}. ] Hence [ g(\sigma+t) = \alpha^{-1}\ln\bigl(\alpha(e^t-e^{-\sigma})\bigr)-\alpha^{-1}\ln\beta-\ln\sigma-\ln!\Bigl(1+\frac{t}{\sigma}\Bigr) = C + \alpha^{-1}\ln(e^t-e^{-\sigma}) - \ln!\Bigl(1+\frac{t}{\sigma}\Bigr), ] where (C=\alpha^{-1}\sigma-\ln\sigma) is a constant. The derivatives of (g) at (\sigma) are the derivatives at (0) of [ F(t)=\alpha^{-1}\ln(e^t-e^{-\sigma}),\qquad G(t)=-\ln!\Bigl(1+\frac{t}{\sigma}\Bigr). ]

For (|t|<\sigma) we expand [ F'(t)=\alpha^{-1}\frac{e^t}{e^t-e^{-\sigma}} = \alpha^{-1}\frac{1}{1-e^{-\sigma}e^{-t}} = \alpha^{-1}\sum_{m=0}^{\infty}e^{-m\sigma}e^{-mt}. ] Differentiating term by term gives, for (k\ge 1), [ F^{(k)}(t)=\alpha^{-1}\sum_{m=0}^{\infty}(-m)^{k-1}e^{-m\sigma}e^{-mt}. ] Thus [ F^{(n+1)}(0)=\alpha^{-1}\sum_{m=1}^{\infty}(-m)^n e^{-m\sigma} \qquad (n\ge 0,; \text{the }m=0\text{ term vanishes for }n\ge 1). ]

For (G) we have [ G^{(k)}(t)=\frac{(-1)^k(k-1)!}{(\sigma+t)^k},\qquad G^{(k)}(0)=\frac{(-1)^k(k-1)!}{\sigma^k}. ] Hence [ G^{(n+1)}(0)=\frac{(-1)^{n+1}n!}{\sigma^{n+1}}. ]

Adding and multiplying by ((-\sigma)^{n+1}) yields [ \begin{aligned} (-\sigma)^{n+1}g^{(n+1)}(\sigma) &= (-\sigma)^{n+1}\alpha^{-1}\sum_{m=1}^{\infty}(-m)^n e^{-m\sigma}

  • (-\sigma)^{n+1}\frac{(-1)^{n+1}n!}{\sigma^{n+1}} \[2mm] &= -\alpha^{-1}\sigma^{n+1}\sum_{m=1}^{\infty}m^n e^{-m\sigma} + n!. \end{aligned} ]

Now set (y=e^{-\sigma}=\beta/\alpha). Using the Eulerian generating function, [ \sum_{m=1}^{\infty}m^n e^{-m\sigma}= \frac{y,A_n(y)}{(1-y)^{n+1}}, \qquad 1-y = 1-\frac{\beta}{\alpha}=\frac{\sigma}{\alpha}. ] Thus [ \alpha^{-1}\sigma^{n+1}\sum_{m=1}^{\infty}m^n e^{-m\sigma} = \alpha^{-1}\sigma^{n+1}\frac{\beta/\alpha}{\bigl(\sigma/\alpha\bigr)^{n+1}}A_n(\beta/\alpha) = \beta\alpha^{n-1}A_n(\beta/\alpha). ] By symmetry of Eulerian numbers, (A_n(x)=x^{n-1}A_n(1/x)); with (x=\beta/\alpha) this gives [ \beta\alpha^{n-1}A_n(\beta/\alpha)=\beta^n A_n(\alpha/\beta) = \sum_{k=0}^{n}\left\langle{n\atop k}\right\rangle\alpha^k\beta^{n-k}. ] Substituting back we obtain the required identity [ (-\sigma)^{n+1}g^{(n+1)}(\sigma)=n!-\sum_{k=0}^{n}\left\langle{n\atop k}\right\rangle\alpha^k\beta^{n-k}. ]

b)

From part (a) we have [ S_n:=\sum_{k=0}^{n}\left\langle{n\atop k}\right\rangle\alpha^k\beta^{n-k} = \alpha^{-1}\sigma^{n+1}\sum_{m=1}^{\infty}m^n e^{-m\sigma}. ] Let (W\sim\operatorname{Exp}(1)) (density (e^{-w}), (w>0)) and define (V=\sigma\lceil W/\sigma\rceil). Then (V) takes values (m\sigma) with probability [ \Pr(V=m\sigma)=e^{-(m-1)\sigma}(1-e^{-\sigma}),\qquad m=1,2,\dots ] Its (n)-th moment is [ \mathbb{E}[V^n]=\sum_{m=1}^{\infty}(m\sigma)^n e^{-(m-1)\sigma}(1-e^{-\sigma}) = \sigma^n(1-e^{-\sigma})e^{\sigma}\sum_{m=1}^{\infty}m^n e^{-m\sigma}. ] Using (\alpha=\sigma/(1-e^{-\sigma})) and (e^{\sigma}=\alpha/\beta) we find [ S_n = \frac{\beta}{\alpha},\mathbb{E}[V^n]. ]

Since (\lceil x\rceil) satisfies (x\le\lceil x\rceil < x+1) for all (x), we have [ W \le V < W+\sigma \quad\text{a.s.} ] Because (x\mapsto x^n) is strictly increasing on ((0,\infty)), [ W^n \le V^n < (W+\sigma)^n \quad\text{a.s.,} ] and the inequalities are strict with probability one. Taking expectations, [ \mathbb{E}[W^n] < \mathbb{E}[V^n] < \mathbb{E}[(W+\sigma)^n]. ] The moments of (W) are (\mathbb{E}[W^k]=k!), so (\mathbb{E}[W^n]=n!). Expanding the right side, [ \mathbb{E}[(W+\sigma)^n] = \sum_{k=0}^{n}\binom{n}{k}\sigma^{n-k}\mathbb{E}[W^k] = \sum_{k=0}^{n}\binom{n}{k}\sigma^{n-k}k! = n!\sum_{j=0}^{n}\frac{\sigma^j}{j!} < n!e^{\sigma}. ] Thus [ n! < \mathbb{E}[V^n] < n!e^{\sigma}. ] Multiplying by (\beta/\alpha=e^{-\sigma}) gives [ \frac{\beta}{\alpha},n! < S_n < n!, ] which is the desired inequality.

c)

Inequality (42) in the text states [ 0 < (-\sigma)^{n+1}g^{(n+1)}(\sigma) < \frac{\sigma}{\alpha},n!. ] By part (a), ((- \sigma)^{n+1}g^{(n+1)}(\sigma) = n! - S_n). Part (b) gives ((\beta/\alpha)n! < S_n < n!). Subtracting from (n!) yields [ 0 < n! - S_n < n! - \frac{\beta}{\alpha}n! = \frac{\alpha-\beta}{\alpha}n! = \frac{\sigma}{\alpha}n!. ] This is exactly (42). ∎

Verification

The identity of part (a) was checked for (n=1,2) by direct differentiation of (g) and by evaluating the Eulerian sum; both matched perfectly. The probabilistic interpretation in part (b) was tested numerically for (\sigma=1, n=2) and satisfied the bounds (2 < \mathbb{E}[V^2] \approx 3.424 < e\cdot2 \approx 5.436). The final inequality (42) was also verified for the same values. The derivations are algebraically self‑consistent and rely only on the stated definitions and standard properties of Eulerian numbers and the exponential distribution.