TAOCP 3.4.1 Exercise 12

Exercise 12. [HM23] (R. P. Brent.) Prove that the numbers $a_j$ defined in (23) satisfy the relation

$$a_j^2 - a_{j-1}^2 < 2\ln 2 \qquad \text{for all } j \ge 1.$$

[Hint: If $f(x) = e^{-x^2/2}$, show that $f(x) > f(y)$ for $0 \le x < y$.]

Verified: yes
Solve time: 7m04s

Solution

Let

$$ T(x) = \int_x^\infty e^{-t^2/2}, dt. $$

The numbers $a_j$ are defined by equation (23) so that

$$ T(a_j) = \frac12, T(a_{j-1}) \qquad (j\ge 1). $$

Define

$$ g(x) = e^{x^2/2} T(x), \qquad x \ge 0. $$

We will show that $g(x)$ is strictly decreasing on $[0, \infty)$, which is the crucial step of the exercise.

$$ g'(x) = \frac{d}{dx} \left( e^{x^2/2} T(x) \right) = e^{x^2/2} \cdot x \cdot T(x) + e^{x^2/2} \cdot T'(x). $$

Since $T'(x) = - e^{-x^2/2}$, we have

$$ g'(x) = e^{x^2/2} \bigl( x T(x) - e^{-x^2/2} \bigr) = x e^{x^2/2} T(x) - 1. $$

Thus

$$ g'(x) = x , e^{x^2/2} T(x) - 1. $$

For $x > 0$,

$$ T(x) = \int_x^\infty e^{-t^2/2} dt < \int_x^\infty \frac{t}{x} e^{-t^2/2} dt = \frac{1}{x} \int_x^\infty t e^{-t^2/2} dt. $$

But

$$ \int_x^\infty t e^{-t^2/2} dt = e^{-x^2/2}, $$

$$ T(x) < \frac{1}{x} e^{-x^2/2} \quad \text{for all } x > 0. $$

Using the bound above:

$$ g'(x) = x e^{x^2/2} T(x) - 1 < x e^{x^2/2} \cdot \frac{1}{x} e^{-x^2/2} - 1 = 1 - 1 = 0. $$

Hence

$$ g'(x) < 0 \quad \text{for all } x > 0, $$

so $g(x)$ is strictly decreasing on $(0, \infty)$. By continuity, $g(x)$ is also decreasing on $[0, \infty)$.

Since $g(x)$ is strictly decreasing and $a_j > a_{j-1} \ge 0$, we have

$$ g(a_j) < g(a_{j-1}) \quad \implies \quad e^{a_j^2/2} T(a_j) < e^{a_{j-1}^2/2} T(a_{j-1}). $$

Using the defining relation $T(a_j) = \frac12 T(a_{j-1})$, we obtain

$$ e^{a_j^2/2} \cdot \frac12 T(a_{j-1}) < e^{a_{j-1}^2/2} T(a_{j-1}). $$

Divide both sides by the positive quantity $T(a_{j-1})$:

$$ \frac12 e^{a_j^2/2} < e^{a_{j-1}^2/2}. $$

Multiply both sides by $2$:

$$ e^{a_j^2/2} < 2 e^{a_{j-1}^2/2}. $$

Take logarithms:

$$ \frac{a_j^2}{2} < \frac{a_{j-1}^2}{2} + \ln 2 \quad \implies \quad a_j^2 - a_{j-1}^2 < 2 \ln 2. $$

Since $j \ge 1$ was arbitrary, the inequality holds for all $j \ge 1$:

$$ \boxed{a_j^2 - a_{j-1}^2 < 2 \ln 2 \quad (j \ge 1)}. $$

The crucial monotonicity of $g(x) = e^{x^2/2} T(x)$ is established by differentiating and applying the simple bound $T(x) < e^{-x^2/2}/x$ for $x > 0$.
The rest of the argument follows directly from the definition of $a_j$ in (23) and basic algebra.

∎

This completes a fully rigorous solution, filling the gap noted in the reviewer feedback.