TAOCP 5.2.2 Exercise 47

Exercise 47. [HM21] Prove that $\sum_{j \ge 1} (n/2^j) e^{-n/2^j}$ is a bounded function of $n$.

Verified: no
Solve time: 4m07s

Solution

We need to prove that the function [ S(n) = \sum_{j=1}^{\infty} \frac{n}{2^j} e^{-n/2^j} ] is bounded for all (n > 0). (If (n \le 0), the sum is trivially zero or not defined; we consider (n>0).)

Define (f(x) = x e^{-x}) for (x \ge 0). Then (S(n) = \sum_{j=1}^\infty f(n/2^j)).

First, if (0 < n \le 1), then (n/2^j \le 1/2) for all (j\ge 1), and on ([0,1]) we have (f(x) \le x). Hence [ S(n) \le \sum_{j=1}^\infty \frac{n}{2^j} = n \le 1. ]

Now assume (n > 1). Let (m = \lfloor \log_2 n \rfloor) so that (2^m \le n < 2^{m+1}). Write (n = 2^m \theta) with (\theta \in [1,2)). Split the sum at (j = m): [ S(n) = \sum_{j=1}^m f(n/2^j) + \sum_{j=m+1}^\infty f(n/2^j). ]

First sum. For (1 \le j \le m), set (k = m - j) ((k = 0,1,\dots,m-1)). Then [ \frac{n}{2^j} = \frac{2^m \theta}{2^{m-k}} = \theta 2^k. ] Since (\theta \ge 1), we have (\theta 2^k \ge 2^k \ge 1). The function (f(x) = x e^{-x}) is decreasing for (x \ge 1) (its derivative is (f'(x) = (1-x)e^{-x} \le 0)). Therefore [ f(\theta 2^k) \le f(2^k) = 2^k e^{-2^k}. ] Thus [ \sum_{j=1}^m f(n/2^j) = \sum_{k=0}^{m-1} f(\theta 2^k) \le \sum_{k=0}^{m-1} 2^k e^{-2^k} \le \sum_{k=0}^\infty 2^k e^{-2^k}. ] The series (\sum_{k=0}^\infty 2^k e^{-2^k}) converges because its terms are positive and, for instance, [ \frac{2^{k+1} e^{-2^{k+1}}}{2^k e^{-2^k}} = 2 e^{-2^k} \to 0 \quad (k\to\infty), ] so the ratio test gives absolute convergence. Let (C = \sum_{k=0}^\infty 2^k e^{-2^k} < \infty).

Second sum. For (j > m), set (t = j - m \ge 1). Then [ \frac{n}{2^j} = \frac{\theta}{2^t} \le \frac{2}{2} = 1 \quad (\text{since } \theta < 2). ] For (0 \le x \le 1) we have (e^{-x} \le 1), hence (f(x) \le x). Consequently [ \sum_{j=m+1}^\infty f(n/2^j) = \sum_{t=1}^\infty f!\left(\frac{\theta}{2^t}\right) \le \sum_{t=1}^\infty \frac{\theta}{2^t} = \theta < 2. ]

Combining the two parts, [ S(n) \le C + 2 \qquad \text{for all } n > 1. ] Together with the bound (S(n) \le 1) for (0 < n \le 1), we conclude that (S(n)) is bounded by (\max(1, C+2)) for all (n > 0).

This completes the proof. ∎