TAOCP 5.2.1 Exercise 18

Exercise 18. [HM2] For large $N$ the sum (6) can be estimated as

$$\frac{1}{4} \frac{N^2}{h_{t-1}} - \frac{\sqrt{\pi}}{8} \left( \frac{N^{3/2} h_{t-1}^{1/2}}{h_{t-2}} + \cdots + \frac{N^{3/2} h_1^{1/2}}{h_0} \right).$$

What real values of $h_{t-1}, \ldots, h_0$ minimize this expression when $N$ and $t$ are fixed and $h_0 = 1$?

Verified: no
Solve time: 7m44s

We minimize the asymptotic estimate for the sum (6): [ E = \frac{N^2}{4h_{t-1}} + \frac{\sqrt{\pi}}{8},N^{3/2} \sum_{k=1}^{t-1} \frac{h_k^{1/2}}{h_{k-1}}, ] where (N) and (t) are fixed, (h_0 = 1), and (h_1,\dots,h_{t-1} > 0) are real variables.

Setting the partial derivatives to zero gives the necessary conditions.

For (k = t-1): [ \frac{\partial E}{\partial h_{t-1}} = -\frac{N^2}{4}h_{t-1}^{-2}

\frac{\sqrt{\pi}}{8}N^{3/2}\cdot\frac{1}{2}h_{t-1}^{-1/2}h_{t-2}^{-1} = 0 ] [ \Longrightarrow\quad h_{t-1}^{3/2} = \frac{4}{\sqrt{\pi}},N^{1/2},h_{t-2}. \tag{1} ]

For (1 \le k \le t-2): [ \frac{\partial E}{\partial h_k} = \frac{\sqrt{\pi}}{8}N^{3/2}\Bigl( \frac{1}{2}h_k^{-1/2}h_{k-1}^{-1} - h_{k+1}^{1/2}h_k^{-2} \Bigr) = 0 ] [ \Longrightarrow\quad h_{k+1} = \frac{1}{4},h_k^3 h_{k-1}^{-2}. \tag{2} ]

Equation (2) also holds for (k = t-2) (it comes from (\partial E/\partial h_{t-2}=0)), so the recurrence is valid for all (k=1,\dots,t-2).

Let (x_k = \ln h_k). Then (2) becomes the linear recurrence [ x_{k+1} - 3x_k + 2x_{k-1} = -\ln 4. ] Its characteristic roots are (1) and (2); a particular solution is (k\ln 4). Hence [ x_k = A + B\cdot 2^k + k\ln 4. ] The condition (h_0 = 1) ((x_0 = 0)) gives (A + B = 0), so (A = -B). Thus [ x_k = B(2^k - 1) + k\ln 4, \qquad\text{and}\qquad h_k = 4^k \exp\bigl(B(2^k - 1)\bigr) \quad (k = 0,\dots,t-1). ]

Now use the boundary condition (1) with the expressions for (h_{t-1}) and (h_{t-2}): [ 4^{t-1} \exp\bigl(B(2^{t-1}-1)\bigr) = \left(\frac{4}{\sqrt{\pi}}\right)^{2/3} N^{1/3} \left(4^{t-2} \exp\bigl(B(2^{t-2}-1)\bigr)\right)^{2/3}. ] Taking logarithms and multiplying by 3: [ 3(t-1)\ln 4 + 3B(2^{t-1}-1) = 2\ln 4 - \ln\pi + \ln N + 2(t-2)\ln 4 + 2B(2^{t-2}-1). ] Collecting the (B)-terms gives (B(2^t - 1)); collecting the constants gives (\ln N - \ln\pi + (1-t)\ln 4). Therefore [ B = \frac{\ln N - \ln\pi + (1-t)\ln 4}{2^t - 1}. ]

Substituting back, [ h_k = 4^k \exp\left( \frac{2^k - 1}{2^t - 1}\bigl(\ln N - \ln\pi + (1-t)\ln 4\bigr) \right) = 4^k \left(\frac{N}{\pi,4^{t-1}}\right)^{\frac{2^k - 1}{2^t - 1}}, \qquad k = 0,1,\dots,t-1. ]

Because (E \to +\infty) as any (h_k \to 0^+) or (h_k \to +\infty) (with the others fixed), and (E) is continuous on the positive orthant, the unique stationary point is the global minimum.

[ \boxed{h_k = 4^k \left( \frac{N}{\pi,4^{t-1}} \right)^{\frac{2^k - 1}{2^t - 1}} \quad (k = 0,1,\dots,t-1)} ] ∎