University Mathematics — Year 2 · Bachelor Year 2

6Comparison of Functions

Asymptotic analysis — the art of replacing a complicated quantity by a simple one plus a controlled error — was begun in the Year 1 volume with Taylor expansions. This chapter makes it a discipline of its own: expansions along general scales, the series–integral comparison with its full asymptotic force, Stirling’s formula (proved completely), and the systematic study of implicitly defined sequences. These techniques are the daily bread of asymptotic analysis, and every later chapter that estimates anything — series, integrals, probabilities — eats from this table.

6.1 Comparison relations and scales

Definition 6.1

Near a point $a$ ( $a \in \R$ or $\pm\infty$ ), for functions (or sequences, with $n \to \infty$ ): $f = o(g)$ , $f = O(g)$ , $f \sim g$ as in the Year 1 volume. A comparison scale at $a$ is a family of positive functions, pairwise comparable, totally ordered by $o(\cdot)$ — the standard scale at $+\infty$ being

x^{\alpha} (\ln x)^{\beta} \qquad (\alpha, \beta \in \R),

ordered lexicographically in $(\alpha, \beta)$ , refined when needed by exponentials $\eu^{\gamma x}$ .

Definition 6.2 (Asymptotic expansion)

$f$ admits the asymptotic expansion

f = c_1 \varphi_1 + c_2\varphi_2 + \dots + c_k \varphi_k + o(\varphi_k) \qquad (\varphi_{i+1} = o(\varphi_i) \text{ in the scale})

when the successive remainders satisfy the displayed estimates. The coefficients are then unique: $c_1 = \lim f/\varphi_1$ , and inductively $c_{i+1} = \lim\,(f - \sum_{j \leq i} c_j\varphi_j)/\varphi_{i+1}$ .

Example 6.3

Taylor expansions are asymptotic expansions along the scale $(x - a)^k$ at $a$ . But the notion is strictly wider: at $+\infty$ ,

\frac{1}{x - \ln x} = \frac1x \cdot \frac{1}{1 - \frac{\ln x}{x}} = \frac1x + \frac{\ln x}{x^2} + o\Bigl(\frac{\ln x}{x^2}\Bigr),

an expansion along the mixed scale — no Taylor theorem applies, only the geometric expansion and the calculus of $o$ ’s.

Example 6.4 (The standard scale is really ordered)

The lexicographic claim of Definition 6.1 needs one line of proof per case. Compare $x^{\alpha}(\ln x)^{\beta}$ and $x^{\alpha'}(\ln x)^{\beta'}$ at $+\infty$ . If $\alpha < \alpha'$ : the ratio is $x^{\alpha - \alpha'}(\ln x)^{\beta - \beta'} \to 0$ , because a negative power of $x$ crushes any power of $\ln x$ (set $x = \eu^t$ : $\eu^{(\alpha - \alpha')t}\,t^{\beta - \beta'} \to 0$ by the exponential-beats-polynomial limit of the Year 1 volume). If $\alpha = \alpha'$ and $\beta < \beta'$ : the ratio is $(\ln x)^{\beta - \beta'} \to 0$ directly. So the pairs $(\alpha, \beta)$ , ordered lexicographically, order the scale by $o(\cdot)$ — and the substitution $x = \eu^t$ is the one-size-fits-all trick for mixed power-log comparisons.

Example 6.5 (Ranking a menagerie)

Scales must be ordered; here is the standard drill. At $+\infty$ , compare $n^{10}$ , $\eu^{\sqrt{\ln n}\,\cdot\,\sqrt n}$ , $2^n$ and $n^{\ln n}$ by taking logarithms:

10\ln n \;\ll\; (\ln n)^2 \;\ll\; \sqrt{n\ln n} \;\ll\; n\ln 2 ,

where $a_n \ll b_n$ means $a_n = o(b_n)$ ; the second entry is $\ln(n^{\ln n})$ . Exponentials preserve these strict gaps (if $\ln u_n - \ln v_n \to -\infty$ then $u_n/v_n \to 0$ ), so

n^{10} = o\bigl(n^{\ln n}\bigr), \qquad n^{\ln n} = o\bigl(\eu^{\sqrt{n\ln n}}\bigr), \qquad \eu^{\sqrt{n\ln n}} = o(2^n) .

The moral, twice over: always compare through logarithms (differences of logs, not ratios of logs), and never conclude $u_n \sim v_n$ from $\ln u_n \sim \ln v_n$ — the pair $n^{10}$ and $n^{\ln n}$ has $\ln$ -ratio tending to $\infty$ , but $2^n$ and $4^n$ have $\ln$ -ratio exactly $2$ and are wildly inequivalent.

6.2 Series–integral comparison, asymptotically

Theorem 6.6

Let $f$ be continuous, positive, decreasing on $\intco{1}{+\infty}$ .

If $\int_1^{\infty} f$ converges, the remainders satisfy

$\int_{n+1}^{\infty} f \;\leq\; \sum_{k > n} f(k) \;\leq\; \int_{n}^{\infty} f .$
If $\int_1^\infty f$ diverges, the partial sums satisfy $\sum_{k=1}^{n} f(k) = \int_1^n f + C + o(1)$ for some constant $C$ : the difference $\sum_{k \leq n} f(k) - \int_1^n f$ converges.

Proof. The bracketing $f(k+1) \leq \int_k^{k+1} f \leq f(k)$ (decrease) was the Year 1 device; summing over $k \geq n+1$ , resp. $k \geq n$ , gives (1). For (2), set $u_k = f(k) - \int_k^{k+1} f$ : by the bracketing, $0 \leq u_k \leq f(k) - f(k+1)$ , so the partial sums of $\sum u_k$ are bounded by the telescoping $f(1) - f(n+1) \leq f(1)$ : the series converges. Moreover the sequence $\bigl(\int_n^{n+1} f\bigr)_n$ is nonincreasing ( $f$ decreases) and nonnegative, hence convergent. Writing

\sum_{k=1}^{n} f(k) - \int_1^n f = \sum_{k=1}^{n} u_k + \int_n^{n+1} f ,

the right side converges as $n \to \infty$ : the difference converges to a constant $C$ , which is statement (2). ∎

Example 6.7 (The harmonic expansion)

For $f(t) = \frac1t$ : $H_n = \ln n + \gamma + o(1)$ , recovering Euler’s constant (Year 1 volume) with a cleaner proof. Pushing one order further (Exercise 6.3):

H_n = \ln n + \gamma + \frac{1}{2n} + o\Bigl(\frac1n\Bigr).

Numbers make the gain visible at $n = 10$ : $H_{10} = 2.928968\dots$ and $\ln 10 = 2.302585\dots$ , so the raw estimate of $\gamma$ is $H_{10} - \ln 10 = 0.626383$ , off by $0.049$ ; subtracting the correction $\frac1{20}$ gives $0.576383$ , off from $\gamma = 0.577216$ by only $8.3\cdot10^{-4}$ — which is itself the next term $\frac{1}{12\cdot100}$ of the expansion, as the weekend problem proves (question 8).

Example 6.8 (A crude $\ln(n!)$ without Stirling)

The bracketing device alone already locates $\ln(n!)$ . Since $\ln$ increases,

\int_{k-1}^{k}\ln t\,\dd t \;\leq\; \ln k \;\leq\; \int_{k}^{k+1}\ln t\,\dd t ,

and summing over $k = 2, \dots, n$ (with $\int_1^n\ln = n\ln n - n + 1$ ):

n\ln n - n + 1 \;\leq\; \ln(n!) \;\leq\; (n+1)\ln(n+1) - n .

Both fences are $n\ln n - n + O(\ln n)$ : hence $\ln(n!) = n\ln n - n + O(\ln n)$ , and in particular $\ln(n!) \sim n\ln n$ . What Stirling adds is the next two rungs — the $\frac12\ln n$ and the constant $\ln\sqrt{2\pi}$ — which cost the finer telescoping of Theorem 6.13. Knowing which precision each tool buys is half of asymptotic craft.

Example 6.9 (Cancellation demands expansions)

Compute the limit of $\sqrt{n^2 + n} - n$ . Both terms are $\sim n$ , and “ $\sim n - n$ ” is meaningless: equivalents cannot be subtracted. Expand instead:

\sqrt{n^2 + n} - n = n\Bigl(\sqrt{1 + \tfrac1n} - 1\Bigr) = n\Bigl(\frac{1}{2n} - \frac{1}{8n^2} + O\Bigl(\frac1{n^3}\Bigr)\Bigr) = \frac12 - \frac{1}{8n} + O\Bigl(\frac1{n^2}\Bigr) :

limit $\frac12$ , with the approach speed $\frac1{8n}$ as a bonus. The mechanism deserves a name: a difference of two large equivalent quantities lives entirely in their next terms, so one must expand to the first order at which the two sides differ — and carry the remainder to certify that nothing else survives at that order.

Example 6.10 (A divergent comparison, worked)

For $f(t) = \frac{1}{t\ln t}$ on $\intco{2}{+\infty}$ (continuous, positive, decreasing): $\int_2^x f = \ln\ln x - \ln\ln 2 \to \infty$ , so by Theorem 6.6 (2),

\sum_{k=2}^{n}\frac{1}{k\ln k} = \ln\ln n + C + o(1)

for some constant $C$ . Two lessons. First, the divergence is real but glacial: the partial sum first exceeds $4$ around $n \approx \eu^{\eu^{4 - C}}$ , astronomically large. Second, the shape $\ln\ln n$ was delivered by an antiderivative, not guessed: for monotone terms, the integral is the canonical summing device, and the constant $C$ — like Euler’s $\gamma$ — is the memory of the initial terms.

6.3 Stirling’s formula

Lemma 6.11 (Wallis integrals, revisited)

Let $W_n = \int_0^{\pi/2} \sin^n t\,\dd t$ . Then $nW_nW_{n-1} = \frac\pi2$ for $n \geq 1$ , $(W_n)$ decreases, and $W_n \sim \sqrt{\dfrac{\pi}{2n}}$ .

Proof. Integration by parts gives $nW_n = (n-1)W_{n-2}$ ( $n \geq 2$ ), so $nW_nW_{n-1}$ is constant in $n$ , equal to $1 \cdot W_1 W_0 = \frac\pi2$ . Decrease: $\sin^{n+1} \leq \sin^n$ on $\intcc{0}{\frac\pi2}$ . The squeeze, in detail: monotonicity gives $W_{n+1} \leq W_n \leq W_{n-1}$ , and dividing by $W_{n-1} > 0$ ,

\frac{n}{n+1} = \frac{W_{n+1}}{W_{n-1}} \leq \frac{W_n}{W_{n-1}} \leq 1 ,

the left identity from the recurrence at index $n + 1$ . Both bounds tend to $1$ : $W_n \sim W_{n-1}$ , whence

nW_n^2 \sim nW_nW_{n-1} = \frac\pi2 \qquad\Longrightarrow\qquad W_n \sim \sqrt{\frac{\pi}{2n}} .

∎

Example 6.12 (The first Wallis integrals)

From $W_0 = \frac\pi2$ , $W_1 = 1$ and the recurrence $nW_n = (n-1)W_{n-2}$ :

W_2 = \frac\pi4, \qquad W_3 = \frac23, \qquad W_4 = \frac{3\pi}{16}, \qquad W_5 = \frac{8}{15}, \qquad W_6 = \frac{5\pi}{32}.

Even indices carry a $\pi$ , odd ones are rational — the two interleaved products of the closed forms. Numerically $W_6 \approx 0.4909$ against the asymptotic $\sqrt{\pi/12} \approx 0.5116$ : at $n = 6$ the equivalent is already within $5\%$ , and the product identity is exact at every $n$ : $6\,W_6W_5 = 6\cdot\frac{5\pi}{32}\cdot\frac8{15} = \frac\pi2$ . Small tables like this one are the cheapest way to catch an algebra slip before it infects an asymptotic argument.

Theorem 6.13 (Stirling)

n! \;\sim\; \sqrt{2\pi n}\, \Bigl(\frac{n}{\eu}\Bigr)^{\!n} .

Proof. Step 1: $n! \sim C \sqrt n\, (n/\eu)^n$ for some constant $C > 0$ . Set

d_n = \ln(n!) - \Bigl(n + \frac12\Bigr)\ln n + n .

Then

d_n - d_{n+1} = \Bigl(n + \frac12\Bigr) \ln\frac{n+1}{n} - 1 = \Bigl(n + \frac12\Bigr)\Bigl(\frac1n - \frac{1}{2n^2} + \frac{1}{3n^3} + o\bigl(n^{-3}\bigr)\Bigr) - 1 = \frac{1}{12n^2} + o\Bigl(\frac{1}{n^2}\Bigr),

by the Taylor expansion of $\ln(1 + \frac1n)$ . The series $\sum (d_n - d_{n+1})$ thus converges absolutely (comparison with $\sum n^{-2}$ ), so $(d_n)$ converges, say to $d$ ; exponentiating, $n! \sim C\sqrt n\,(n/\eu)^n$ with $C = \eu^{d}$ .

Step 2: $C = \sqrt{2\pi}$ via Wallis. The closed form $W_{2p} = \frac{(2p)!}{4^p (p!)^2}\cdot\frac\pi2$ (from the recurrence, Year 1 computation redone in Lemma 6.11’s setting) combines with Step 1:

W_{2p} \sim \frac{C\sqrt{2p}\,(2p/\eu)^{2p}} {4^p\,\bigl(C\sqrt p\,(p/\eu)^p\bigr)^2}\cdot\frac{\pi}{2} = \frac{\sqrt{2p}}{C\,p}\cdot\frac{\pi}{2} = \frac{\pi}{C}\cdot\frac{1}{\sqrt{2p}} .

Comparing with $W_{2p} \sim \sqrt{\frac{\pi}{4p}}$ (Lemma 6.11): $\frac{\pi}{C\sqrt{2p}} = \sqrt{\frac{\pi}{4p}}\,(1 + o(1))$ forces $C = \pi \sqrt{\frac{4p}{2p\,\pi}} = \sqrt{2\pi}$ . ∎

Example 6.14 (Central binomial coefficient)

\binom{2n}{n} = \frac{(2n)!}{(n!)^2} \sim \frac{\sqrt{4\pi n}\,(2n/\eu)^{2n}}{2\pi n\,(n/\eu)^{2n}} = \frac{4^n}{\sqrt{\pi n}} :

the probability that a symmetric random walk returns to $0$ at time $2n$ is $\sim \frac{1}{\sqrt{\pi n}}$ — an announcement of Chapter 22.

Remark 6.15 (Perspectives within this volume)

Every quantitative chapter ahead speaks this chapter’s language. Chapter 7 classifies series by comparing terms to the scale $n^{-\alpha}(\ln n)^{-\beta}$ — its weekend problem maps that frontier completely. Chapter 9 does the same for improper integrals, with the identical scale in the continuous variable. Chapter 11 computes radii of convergence from $\limsup\abs{a_n}^{1/n}$ , an equivalent-of- $n$ -th-roots exercise where Stirling is the standard key ( $\sqrt[n]{n!} \sim \frac n\eu$ , Exercise 6.4). And the probability chapters cash Stirling directly: the local estimates of Chapter 22 for binomial coefficients are Example 6.14 and Example 6.21 verbatim. Asymptotics is not a chapter here; it is the volume’s accent.

Method 6.16 (The bootstrap checklist)

Before trusting a bootstrapped expansion, audit four points. (1) Existence first: the root or sequence must be pinned down (monotonicity, intermediate values) before any expansion — symbols without referents expand beautifully and mean nothing. (2) One order per pass: each substitution may only be trusted to the order of the estimate fed in; extracting two new terms from one pass is the classic source of wrong coefficients. (3) Remainders ride along: carry the $o(\cdot)$ through every algebraic step and let absorption (smaller terms swallowed by larger remainders) happen at the end, explicitly. (4) Numerical audit: evaluate at one honest value of $n$ ; a coefficient error survives algebraic re-derivation surprisingly often, and almost never survives arithmetic.

Remark 6.17 (Common pitfalls)

(i) Equivalents add badly: from $u_n \sim n + \ln n$ and $v_n \sim -n$ one may not conclude $u_n + v_n \sim \ln n$ ; cancellations demand expansions with explicit remainders, never bare equivalents. (ii) Never exponentiate an equivalence: $n + 1 \sim n$ but $\eu^{n+1} \not\sim \eu^n$ ; the safe direction is taking logarithms of equivalents tending to $+\infty$ (this chapter’s weekend problem, question 24). (iii) An asymptotic expansion is attached to a scale: writing $f = \frac1x + o\bigl(\frac1{x^2}\bigr)$ claims more than $f = \frac1x + o\bigl(\frac1x\bigr)$ , and mixing the two invalidates subsequent algebra. (iv) In bootstraps, substitute the whole current expansion, remainder included — dropping an $o(\cdot)$ mid-pass produces plausible but wrong coefficients. (v) The series–integral comparison needs monotonicity: for oscillating terms it fails outright (compare $\sum\frac{\sin k}k$ , Chapter 7).

Example 6.18 (Stirling in numbers)

At $n = 10$ : the formula gives $\sqrt{20\pi}\,(10/\eu)^{10} \approx 3\,598\,696$ against $10! = 3\,628\,800$ : relative error $8.3\cdot10^{-3}$ , remarkable for an “asymptotic” statement at $n = 10$ . The error has a structure — the exact refinement $n! = \sqrt{2\pi n}\,(n/\eu)^n\bigl(1 + \frac1{12n} + O(n^{-2})\bigr)$ — whose first correction $\frac1{120} \approx 8.3\cdot10^{-3}$ explains the observed gap almost exactly. The weekend problem’s Euler–Maclaurin machinery is precisely the systematic source of such correction terms.

Remark 6.19 (Where this chapter is used)

Asymptotic comparison is the grammar of everything quantitative downstream: the convergence tests and Bertrand panorama of Chapter 7, the integrability criteria of Chapter 9, the radius-of-convergence computations of Chapter 11, and the limit theorems of Chapter 22 (where Stirling runs the de Moivre–Laplace estimates). The Year 3 volume industrializes the one idea we prove by hand here — extract the main term, bound the rest — into the Laplace method and dominated convergence.

Example 6.20 (An integral compared to itself: $\int_2^x \frac{\dd t}{\ln t}$ )

The comparison toolbox also runs on integrals. Let $F(x) = \int_2^x\frac{\dd t}{\ln t}$ (the integrand is continuous on $\intco2\infty$ ). Integrate by parts:

F(x) = \Bigl[\frac{t}{\ln t}\Bigr]_2^x + \int_2^x\frac{\dd t}{(\ln t)^2} = \frac{x}{\ln x} + O\Bigl(\int_2^x\frac{\dd t}{(\ln t)^2}\Bigr) + O(1),

and the remainder integral is $o\bigl(\frac{x}{\ln x}\bigr)$ : split it at $\sqrt x$ , bounding by

\int_2^{\sqrt x}\frac{\dd t}{(\ln t)^2} \leq \sqrt x \qquad\text{and}\qquad \int_{\sqrt x}^{x}\frac{\dd t}{(\ln t)^2} \leq \frac{x}{(\ln\sqrt x)^2} = \frac{4x}{(\ln x)^2} .

Hence $F(x) \sim \frac{x}{\ln x}$ . Readers who met the prime number theorem in this chapter’s weekend problem will recognize $F$ : it is the logarithmic integral, the better estimator of $\pi(x)$ , and the computation shows it agrees with $\frac{x}{\ln x}$ to first order.

Example 6.21 (Stirling on a lopsided binomial)

The same three-factorial routine as for Example 6.14 gives, for $\binom{3n}{n} = \frac{(3n)!}{n!\,(2n)!}$ :

\binom{3n}{n} \sim \frac{\sqrt{6\pi n}\,(3n/\eu)^{3n}} {\sqrt{2\pi n}\,(n/\eu)^{n}\cdot\sqrt{4\pi n}\,(2n/\eu)^{2n}} = \sqrt{\frac{3}{4\pi n}}\, \Bigl(\frac{27}{4}\Bigr)^{\!n} .

The exponential rate $\frac{27}4 = \frac{3^3}{2^2}$ is $\eu^{3n\,H(1/3)}$ in the entropy notation of information theory: lopsided binomials grow strictly slower than the central $4^n$ per two steps — here $(27/4)^{1/3} \approx 1.89 < 2$ per step. Every binomial asymptotic in combinatorics and probability (Chapter 22) is this one computation with different weights.

6.4 Implicitly defined sequences

Method 6.22

To find the asymptotics of solutions $x_n$ of an equation $F(x, n) = 0$ :

Localize: prove existence and uniqueness of $x_n$ in a definite interval (monotonicity, intermediate value theorem), and find its crude behavior (limit, order of growth).
Bootstrap: substitute the crude form $x_n = (\text{main term})(1 + \varepsilon_n)$ into the equation and solve for the next order of $\varepsilon_n$ ; repeat, each pass refining one order.

Example 6.23

For $n \geq 1$ , the equation $\tan x = x$ has exactly one solution $x_n$ in $\intoo{n\pi - \frac\pi2}{n\pi + \frac\pi2}$ (the function $\tan x - x$ increases from $-\infty$ to $+\infty$ there, its derivative being $\tan^2 x \geq 0$ ). Crude: $x_n = n\pi + \frac\pi2 - y_n$ with $y_n \in \intoo{0}{\pi}$ ; since $x_n \to \infty$ and $\tan x_n = x_n \to +\infty$ , $x_n$ approaches the asymptote from the left: $y_n \to 0$ . Bootstrap: $\tan x_n = \cot y_n = \frac{1}{\tan y_n} \sim \frac{1}{y_n}$ , and the equation $\cot y_n = x_n \sim n\pi$ gives $y_n \sim \frac{1}{n\pi}$ . Hence

x_n = n\pi + \frac\pi2 - \frac{1}{n\pi} + o\Bigl(\frac1n\Bigr),

and the process continues to any order (Exercise 6.6).

Example 6.24 (A second run of the method)

Solve $x + \ln x = n$ asymptotically. Localize: $x \mapsto x + \ln x$ increases from $-\infty$ to $+\infty$ on $\intoo{0}{+\infty}$ : a unique root $x_n$ , and $x_n \to \infty$ . Crude: $\ln x_n = o(x_n)$ gives $x_n \sim n$ . Bootstrap: from $x_n = n - \ln x_n$ and $\ln x_n = \ln n + o(1)$ (logarithms of equivalents, both sides $\to \infty$ ):

x_n = n - \ln n + o(1) ;

one more pass, with $\ln x_n = \ln\bigl(n - \ln n + o(1)\bigr) = \ln n - \frac{\ln n}{n} + o\bigl(\frac{\ln n}n\bigr)$ :

x_n = n - \ln n + \frac{\ln n}{n} + o\Bigl(\frac{\ln n}{n}\Bigr).

(Check at $n = 100$ : the root is $x \approx 95.4415$ ; the three-term formula gives $100 - 4.6052 + 0.0461 = 95.4409$ , the two-term one $95.3948$ — each pass gains the predicted order.) Same loop, third landscape: the method of Method 6.22 does not care what the equation looks like, only that each pass isolates the dominant unknown.

6.5 Exercises

Exercise 6.1 ★

Expand at $+\infty$ , two terms beyond the leading one:

\sqrt{x^2 + x + 1} , \qquad \ln(x^2 + x) - 2\ln x, \qquad \frac{x + \sin x}{x - \ln x} .

Solution

Solution of Exercise 6.1.

$\sqrt{x^2 + x + 1} = x\sqrt{1 + \tfrac1x + \tfrac{1}{x^2}} = x + \frac12 + \frac38\cdot\frac1x + o\bigl(\frac1x\bigr)$ (binomial expansion: $\frac12 u - \frac18 u^2$ with $u = \frac1x + \frac{1}{x^2}$ gives $\frac{1}{2x} + \frac{1}{2x^2} - \frac{1}{8x^2} = \frac{1}{2x} + \frac{3}{8x^2}$ , then multiply by $x$ ).

$\ln(x^2 + x) - 2\ln x = \ln\bigl(1 + \tfrac1x\bigr) = \frac1x - \frac{1}{2x^2} + o\bigl(\frac{1}{x^2}\bigr)$ .

Third function: expand each factor,

\frac{x + \sin x}{x - \ln x} = \Bigl(1 + \frac{\sin x}{x}\Bigr) \Bigl(1 + \frac{\ln x}{x} + \frac{(\ln x)^2}{x^2} + O\Bigl(\frac{(\ln x)^3}{x^3}\Bigr)\Bigr).

Order the contributions on the scale at $+\infty$ : $\frac{\ln x}{x} \gg \frac{1}{x} \geq \bigl|\frac{\sin x}{x}\bigr| \gg \frac{(\ln x)^2}{x^2}$ . The two terms after the leading $1$ are therefore $\frac{\ln x}{x}$ , then the bounded-oscillation term $\frac{\sin x}{x}$ :

\frac{x + \sin x}{x - \ln x} = 1 + \frac{\ln x}{x} + \frac{\sin x}{x} + O\Bigl(\frac{(\ln x)^2}{x^2}\Bigr).

Exercise 6.2 ★

Give the nature (convergence/divergence) and, when divergent, the leading asymptotics of $\sum_{k \leq n} k^\alpha$ for $\alpha > -1$ , $\alpha = -1$ , $\alpha < -1$ , via Theorem 6.6.

Solution

Solution of Exercise 6.2.

$f(t) = t^\alpha$ ( $t \geq 1$ ).

$\alpha > -1$ : divergence, and by Theorem 6.6 (2), $\sum_{k\leq n} k^\alpha = \frac{n^{\alpha+1}}{\alpha+1} + C + o(1)$ if $\alpha < 0$ (where $f$ decreases); for $\alpha \geq 0$ ( $f$ increasing) the same bracketing with reversed inequalities gives $\sum_{k \leq n} k^\alpha \sim \frac{n^{\alpha + 1}}{\alpha + 1}$ .

$\alpha = -1$ : $H_n = \ln n + \gamma + o(1)$ (Example 6.7).

$\alpha < -1$ : convergence, with remainder $\sum_{k > n} k^\alpha \sim \frac{n^{\alpha+1}}{-(\alpha+1)}$ by the bracketing (1) (both integral bounds are equivalent to that value).

Exercise 6.3 ★★

Prove $H_n = \ln n + \gamma + \frac{1}{2n} + o\bigl(\frac1n\bigr)$ . (Study $v_n = H_n - \ln n - \gamma$ : show $v_n - v_{n+1} = \frac{1}{2n^2} + O(n^{-3})$ and sum the tail, comparing with $\sum_{k \geq n} \frac{1}{2k^2} \sim \frac{1}{2n}$ — Theorem 6.6 (1).)

Solution

Solution of Exercise 6.3.

Let $v_n = H_n - \ln n - \gamma \to 0$ . Then

v_n - v_{n+1} = \ln\frac{n+1}{n} - \frac{1}{n+1} = \Bigl(\frac1n - \frac{1}{2n^2}\Bigr) - \Bigl(\frac1n - \frac{1}{n^2}\Bigr) + O\Bigl(\frac{1}{n^3}\Bigr) = \frac{1}{2n^2} + O\Bigl(\frac{1}{n^3}\Bigr),

using $\frac{1}{n+1} = \frac1n - \frac{1}{n^2} + O(n^{-3})$ . Since $v_n \to 0$ , telescoping the tail:

v_n = \sum_{k \geq n} (v_k - v_{k+1}) = \sum_{k\geq n} \Bigl(\frac{1}{2k^2} + O(k^{-3})\Bigr) = \frac{1}{2n} + O\Bigl(\frac{1}{n^2}\Bigr),

by Theorem 6.6 (1) applied to $t^{-2}$ (remainder $\sim \frac1n$ , halved) and to $t^{-3}$ . Hence $H_n = \ln n + \gamma + \frac{1}{2n} + o(\frac1n)$ .

Exercise 6.4 ★★

Using Stirling, find equivalents of: $\dfrac{(3n)!}{(n!)^3}$ ; $\;\dfrac{n!}{n^n}$ ; $\;\sqrt[n]{n!}$ (as $\frac n\eu(1 + o(1))$ , made precise to two terms).

Solution

Solution of Exercise 6.4.

Stirling three times:

\frac{(3n)!}{(n!)^3} \sim \frac{\sqrt{6\pi n}\,(3n/\eu)^{3n}} {(2\pi n)^{3/2}\,(n/\eu)^{3n}} = \frac{\sqrt{6}\; 27^{\,n}}{2\pi n} \cdot \frac{1}{\sqrt{2\pi n}}\cdot\sqrt{2\pi n}\; = \frac{\sqrt3\,27^n}{2\pi n} .

(Carefully: $\frac{\sqrt{6\pi n}}{(2\pi n)^{3/2}} = \frac{\sqrt6}{(2\pi n)\sqrt{2\pi n}}\sqrt{\pi n} = \frac{\sqrt3}{2\pi n}$ .)

$\dfrac{n!}{n^n} \sim \sqrt{2\pi n}\,\eu^{-n}$ .

$\sqrt[n]{n!} = \exp\bigl(\frac{\ln n!}{n}\bigr)$ with $\ln n! = n\ln n - n + \frac12\ln(2\pi n) + o(1)$ :

\sqrt[n]{n!} = \exp\Bigl(\ln n - 1 + \frac{\ln(2\pi n)}{2n} + o\Bigl(\frac{\ln n}{n}\Bigr)\Bigr) = \frac{n}{\eu}\Bigl(1 + \frac{\ln(2\pi n)}{2n} + o\Bigl(\frac{\ln n}{n}\Bigr)\Bigr).

Exercise 6.5 ★★

For $n \geq 2$ , prove that $x^n + x = 1$ has a unique solution $x_n \in \intoo{0}{1}$ , that $x_n \to 1$ , and establish

x_n = 1 - \frac{\ln n}{n} + o\Bigl(\frac{\ln n}{n}\Bigr).

(From $x_n^n = 1 - x_n$ : take logarithms and bootstrap with $x_n = 1 - \varepsilon_n$ .)

Solution

Solution of Exercise 6.5.

$g(x) = x^n + x - 1$ increases strictly on $\intcc{0}{1}$ from $-1$ to $1$ : unique root $x_n$ . Since $x_n^n = 1 - x_n \in \intoo{0}{1}$ : if $x_n \leq c < 1$ along a subsequence, then $x_n^n \leq c^n \to 0$ , so $1 - x_n \to 0$ : contradiction with $x_n \leq c$ . Hence $x_n \to 1$ .

Write $x_n = 1 - \varepsilon_n$ , $\varepsilon_n \to 0^+$ . The equation reads $(1 - \varepsilon_n)^n = \varepsilon_n$ , i.e.

n\ln(1 - \varepsilon_n) = \ln \varepsilon_n \quad\Longrightarrow\quad -n\varepsilon_n\bigl(1 + o(1)\bigr) = \ln\varepsilon_n .

So $n\varepsilon_n = -\ln\varepsilon_n\,(1 + o(1)) \to +\infty$ , and taking logarithms again: $\ln n + \ln\varepsilon_n = \ln(-\ln\varepsilon_n) + o(1)$ . Since $\ln(-\ln \varepsilon_n) = o(\ln(1/\varepsilon_n))$ , this gives $\ln\varepsilon_n \sim -\ln n$ , whence $\varepsilon_n = \frac{-\ln\varepsilon_n}{n}(1 + o(1)) \sim \frac{\ln n}{n}$ :

x_n = 1 - \frac{\ln n}{n} + o\Bigl(\frac{\ln n}{n}\Bigr) .

Exercise 6.6 ★★

Push Example 6.23 one order further:

x_n = n\pi + \frac\pi2 - \frac{1}{n\pi} + \frac{1}{2n^2\pi} + o\Bigl(\frac{1}{n^2}\Bigr).

(Write $\cot y_n = x_n$ exactly, expand $\cot y = \frac1y - \frac y3 + o(y)$ and $x_n = n\pi(1 + \frac{1}{2n} - \dots)$ , and identify.)

Solution

Solution of Exercise 6.6.

Exact relation: $\cot y_n = x_n = n\pi + \frac\pi2 - y_n$ , with $y_n \sim \frac{1}{n\pi}$ (Example 6.23). Expand $\cot y = \frac1y - \frac y3 + O(y^3)$ :

\frac{1}{y_n} - \frac{y_n}{3} + O(y_n^3) = n\pi + \frac\pi2 - y_n \quad\Longrightarrow\quad \frac{1}{y_n} = n\pi + \frac\pi2 + O\Bigl(\frac1n\Bigr),

(the terms $-y_n$ and $-\frac{y_n}{3}$ are $O(\frac1n)$ ). Invert:

y_n = \frac{1}{n\pi}\cdot\frac{1}{1 + \frac{1}{2n} + O(n^{-2})} = \frac{1}{n\pi}\Bigl(1 - \frac{1}{2n} + O\Bigl(\frac{1}{n^2}\Bigr)\Bigr) = \frac{1}{n\pi} - \frac{1}{2n^2\pi} + O\Bigl(\frac{1}{n^3}\Bigr).

Hence

x_n = n\pi + \frac{\pi}{2} - y_n = n\pi + \frac\pi2 - \frac{1}{n\pi} + \frac{1}{2n^2\pi} + o\Bigl(\frac{1}{n^2}\Bigr).

Exercise 6.7 ★★

Determine $\lim_{n\to\infty} \dfrac{1}{n!}\sum_{k=0}^{n} k!$ (bound the sum of all terms but the last two), and deduce the asymptotic expansion $\sum_{k \leq n} k! = n!\bigl(1 + \frac1n + O(n^{-2})\bigr)$ .

Solution

Solution of Exercise 6.7.

Split off the two largest terms:

\sum_{k=0}^{n} k! = n! + (n-1)! + \sum_{k \leq n-2} k! , \qquad \sum_{k\leq n-2} k! \leq (n-1)\,(n-2)! = (n-1)! .

So $1 \leq \frac{1}{n!}\sum k! \leq 1 + \frac{2}{n}$ : the limit is $1$ . Refining: $\frac{(n-1)!}{n!} = \frac1n$ and the crude bound $\sum_{k \leq n-2}k! \leq (n-1)!$ can be sharpened the same way: $\sum_{k\leq n-2} k! = (n-2)!\,(1 + O(\frac1n)) = O\bigl(\frac{n!}{n^2}\bigr)$ . Hence

\sum_{k=0}^{n} k! = n!\Bigl(1 + \frac1n + O\Bigl(\frac{1}{n^2}\Bigr)\Bigr).

Exercise 6.8 ★★★

Let $u_0 > 0$ and $u_{n+1} = u_n + \dfrac{1}{u_n}$ . Prove that $u_n \to \infty$ , then that $u_n \sim \sqrt{2n}$ (study $u_n^2$ : its increments are $2 + u_n^{-2}$ ; sum), and refine:

u_n = \sqrt{2n}\Bigl(1 + \frac{\ln n}{8n} + o\Bigl(\frac{\ln n}{n}\Bigr)\Bigr).

(From $u_n^2 = 2n + \sum_{k<n} u_k^{-2} + u_0^2$ and $u_k^2 \sim 2k$ : the sum is $\sim \frac12\ln n$ by Theorem 6.6.)

Solution

Solution of Exercise 6.8.

$(u_n)$ increases; if bounded it would converge to $\ell$ with $\ell = \ell + \frac1\ell$ : absurd. So $u_n \to \infty$ .

Squares: $u_{n+1}^2 = u_n^2 + 2 + u_n^{-2}$ , so

u_n^2 = u_0^2 + 2n + \sum_{k=0}^{n-1} \frac{1}{u_k^2} .

The sum is $o(n)$ (terms tend to $0$ , Cesàro), so $u_n^2 \sim 2n$ and $u_n \sim \sqrt{2n}$ .

Refinement: $\frac{1}{u_k^2} \sim \frac{1}{2k}$ , so by comparison (Theorem 6.6, or equivalents of partial sums of positive series) $\sum_{k<n} u_k^{-2} \sim \frac12 \ln n$ . Hence

u_n^2 = 2n + \frac{\ln n}{2}\,(1 + o(1)) + O(1) \quad\Longrightarrow\quad u_n = \sqrt{2n}\sqrt{1 + \frac{\ln n}{4n} + o\Bigl(\frac{\ln n}{n}\Bigr)} = \sqrt{2n}\Bigl(1 + \frac{\ln n}{8n} + o\Bigl(\frac{\ln n}{n}\Bigr)\Bigr).

Exercise 6.9 ★★★

(A Riemann sum with a twist) Determine the asymptotic behavior of

S_n = \sum_{k=1}^{n} \frac{1}{n + k\ln n} .

(Factor $n$ : $S_n = \frac1n\sum_k \bigl(1 + \frac{k\ln n}{n}\bigr)^{-1}$ ; recognize a Riemann-type sum with a slowly varying parameter $t = \ln n$ , compute $\int_0^1 \frac{\dd u}{1 + tu} = \frac{\ln(1+t)}{t}$ , and conclude $S_n \sim \frac{\ln\ln n}{\ln n}$ .)

Solution

Solution of Exercise 6.9.

Factor $n$ and set $t = \ln n$ :

S_n = \frac1n \sum_{k=1}^{n} \frac{1}{1 + t\,\frac kn} .

For fixed $t$ , the sum is a Riemann sum of $u \mapsto \frac{1}{1 + tu}$ on $\intcc{0}{1}$ ; the function is monotone in $u$ , so the Riemann sum is bracketed by the integral shifted by one mesh:

\int_0^1 \frac{\dd u}{1 + tu} - \frac1n \leq S_n \leq \int_0^1 \frac{\dd u}{1 + tu} + \frac1n

(comparison of a monotone function’s Riemann sums with its integral, valid for each $n$ with its own $t = \ln n$ ). Now $\int_0^1 \frac{\dd u}{1 + tu} = \frac{\ln(1 + t)}{t}$ , and $\frac1n = o\bigl(\frac{\ln t}{t}\bigr)$ : hence

S_n = \frac{\ln(1 + \ln n)}{\ln n} + O\Bigl(\frac 1n\Bigr) \;\sim\; \frac{\ln\ln n}{\ln n} .

Exercise 6.10 ★

Prove the identity $(\ln n)^{\ln n} = n^{\ln\ln n}$ , then rank the following in increasing $o(\cdot)$ order at infinity, with proofs: $n^2$ , $(\ln n)^{\ln n}$ , $2^n$ , $n!$ , $n^n$ .

Solution

Solution of Exercise 6.10.

Identity: $(\ln n)^{\ln n} = \eu^{\ln n\,\ln\ln n} = \bigl(\eu^{\ln n}\bigr)^{\ln\ln n} = n^{\ln\ln n}$ . Ranking: compare logarithms. $\ln(n^2) = 2\ln n$ ; $\ln\bigl((\ln n)^{\ln n}\bigr) = \ln n\ln\ln n$ ; $\ln(2^n) = n\ln2$ ; $\ln(n!) = n\ln n - n + O(\ln n)$ (Stirling, or the cruder bracketing $\ln n! \sim n\ln n$ ); $\ln(n^n) = n\ln n$ . Since $2\ln n = o(\ln n\ln\ln n)$ , $\ln n\ln\ln n = o(n)$ , $n\ln 2 = o(n\ln n - n)$ , and $n \ln n - n \sim n\ln n$ but $n! / n^n \to 0$ (the difference of logs is $-n + O(\ln n) \to -\infty$ ):

n^2 = o\bigl((\ln n)^{\ln n}\bigr),\quad (\ln n)^{\ln n} = o(2^n),\quad 2^n = o(n!),\quad n! = o(n^n).

(For each step: the difference of logarithms tends to $+\infty$ , so the ratio tends to $0$ .)

Exercise 6.11 ★★

(Tail of $\sum 1/k^2$ , two terms) Using the exact telescoping $\sum_{k > n} \frac{1}{k(k+1)} = \frac{1}{n+1}$ and the decomposition $\frac1{k^2} = \frac{1}{k(k+1)} + \frac{1}{k^2(k+1)}$ , prove

\sum_{k > n} \frac{1}{k^2} = \frac1n - \frac{1}{2n^2} + O\Bigl(\frac{1}{n^3}\Bigr).

Solution

Solution of Exercise 6.11.

Decompose $\frac1{k^2} = \frac1{k(k+1)} + \frac1{k^2(k+1)}$ and sum for $k > n$ :

\sum_{k>n}\frac1{k^2} = \frac1{n+1} + \sum_{k>n}\frac{1}{k^2(k+1)} ,

the first sum telescoping exactly ( $\frac1{k(k+1)} = \frac1k - \frac1{k+1}$ ). For the second: $\frac{1}{k^2(k+1)} = \frac1{k^3} + O\bigl(\frac1{k^4}\bigr)$ (since $\frac{1}{k^2(k+1)} - \frac1{k^3} = \frac{-1}{k^3(k+1)}$ ), and by the integral comparison $\sum_{k>n}\frac1{k^3} = \frac1{2n^2} + O\bigl(\frac1{n^3}\bigr)$ , $\sum_{k>n}\frac1{k^4} = O\bigl(\frac1{n^3}\bigr)$ . Hence

\sum_{k>n}\frac1{k^2} = \frac1{n+1} + \frac{1}{2n^2} + O\Bigl(\frac1{n^3}\Bigr) = \frac1n - \frac1{n^2} + \frac{1}{2n^2} + O\Bigl(\frac1{n^3}\Bigr) = \frac1n - \frac{1}{2n^2} + O\Bigl(\frac1{n^3}\Bigr),

using $\frac1{n+1} = \frac1n - \frac1{n^2} + O\bigl(\frac1{n^3}\bigr)$ .

Exercise 6.12 ★★★

Let $u_0 = \frac12$ and $u_{n+1} = u_n + \eu^{-u_n}$ . Prove that $u_n \to \infty$ , then — setting $v_n = \eu^{u_n}$ and showing $v_{n+1} = v_n + 1 + \frac{1}{2v_n} + O\bigl(v_n^{-2}\bigr)$ — establish

u_n = \ln n + \frac{\ln n}{2n} + O\Bigl(\frac1n\Bigr).

Solution

Solution of Exercise 6.12.

$(u_n)$ increases; if it were bounded it would converge to a finite $\ell$ with $\ell = \ell + \eu^{-\ell}$ : impossible. So $u_n \to \infty$ . Let $v_n = \eu^{u_n} \to \infty$ : then

v_{n+1} = \eu^{u_n + \eu^{-u_n}} = v_n\,\eu^{1/v_n} = v_n\Bigl(1 + \frac1{v_n} + \frac1{2v_n^2} + O\bigl(v_n^{-3}\bigr)\Bigr) = v_n + 1 + \frac{1}{2v_n} + O\bigl(v_n^{-2}\bigr).

Summing $v_{k+1} - v_k = 1 + O(1)$ first gives $v_n = n + O(n)$ , hence $v_n \geq cn$ eventually; re-summing with $\frac1{2v_k} = O(\frac1k)$ gives $v_n = n + O(\ln n)$ . One more pass: $\frac{1}{2v_k} = \frac{1}{2k}\bigl(1 + O\bigl(\tfrac{\ln k}k\bigr)\bigr)$ , so

v_n = n + \sum_{k<n}\frac1{2k} + O(1) = n + \frac{\ln n}2 + O(1).

Finally $u_n = \ln v_n = \ln n + \ln\Bigl(1 + \frac{\ln n}{2n} + O\bigl(\tfrac1n\bigr)\Bigr) = \ln n + \frac{\ln n}{2n} + O\bigl(\tfrac1n\bigr)$ .

6.6 Problem: Bootstrapping, from Euler–Maclaurin to the Primes

An implicit or accumulated quantity rarely hands over its asymptotics at once; one extracts them in passes, each pass feeding the previous estimate back into the defining relation. This weekend problem trains that loop on fresh equations, proves the first-order Euler–Maclaurin formula (the trapezoid upgrade of the series–integral comparison, with rigorous error bars), inverts $x\ln x = n$ , and cashes the method’s most famous cheque: from the admitted prime number theorem, the asymptotic law $p_n \sim n\ln n$ of the $n$ -th prime.

Problem 6.1

Weekend problem — the Euler–Maclaurin correction and the asymptotics of the $n$ -th prime

Part I — The bootstrap loop on a fresh equation.

Prove the uniqueness claim of Definition 6.2: if $f = \sum_{i\leq k} c_i\varphi_i + o(\varphi_k) = \sum_{i \leq k} c_i'\varphi_i + o(\varphi_k)$ along the same scale, then $c_i = c_i'$ for all $i$ . Then push the course’s mixed example one rung further:

$\frac{1}{x - \ln x} = \frac1x + \frac{\ln x}{x^2} + \frac{(\ln x)^2}{x^3} + o\Bigl(\frac{(\ln x)^2}{x^3}\Bigr) \qquad (x \to +\infty),$

and explain why no term $\frac{c}{x^2}$ appears.
Show that for every $n \geq 1$ the equation $\eu^x + x = n$ has exactly one real solution $x_n$ , and that $x_n \to +\infty$ with $x_n \sim \ln n$ .
Bootstrap twice:

$x_n = \ln n - \frac{\ln n}{n} - \frac{(\ln n)^2}{2n^2} + o\Bigl(\frac{(\ln n)^2}{n^2}\Bigr).$
Check numerically at $n = 1000$ : compare $x_{1000} \approx 6.90083$ with the one-, two- and three-term values of question 3, to five decimals.

Part II — Euler–Maclaurin, order one.

Prove the trapezoid kernel identity: for $g$ of class $C^2$ on $\intcc{0}{1}$ ,

$\int_0^1 g(t)\,\dd t = \frac{g(0) + g(1)}{2} - \frac12\int_0^1 t(1 - t)\,g''(t)\,\dd t$

(integrate $\frac12 t(1-t)g''$ by parts twice).
Let $f$ be $C^2$ on $\intco{1}{+\infty}$ with $\int_1^\infty \abs{f''} < \infty$ . Show that

$E_n = \sum_{k=1}^{n} f(k) - \int_1^n f - \frac{f(1) + f(n)}{2}$

converges to a constant $E$ , with the tail bound $\abs{E - E_n} \leq \frac18\int_n^\infty\abs{f''}$ : the Euler–Maclaurin formula to first order.
Apply this to $f(t) = \frac1t$ : prove

$H_n = \ln n + \gamma + \frac{1}{2n} + \varepsilon_n, \qquad \abs{\varepsilon_n} \leq \frac{1}{8n^2},$

strengthening Exercise 6.3 (identify the constant with $\gamma$ by comparing with Example 6.7).
Extract the next coefficient: show $\varepsilon_n = -\frac{1}{12n^2} + o\bigl(\frac1{n^2}\bigr)$ (the increments of $E_n$ are $\frac12\int_0^1t(1-t)f''(n+t)\dd t = \frac1{12}f''(n) + o(f''(n))$ ; sum the tail with Theorem 6.6).
Apply question 6 to $f = \ln$ : re-derive in three lines the convergence of $d_n = \ln n! - (n + \frac12)\ln n + n$ (Step 1 of Theorem 6.13), with the bonus error rate $d_n = d + O\bigl(\frac1n\bigr)$ .
Apply question 6 to $f(t) = \frac{1}{\sqrt t}$ : show

$\sum_{k=1}^{n}\frac1{\sqrt k} = 2\sqrt n + c + \frac{1}{2\sqrt n} + O\Bigl(\frac{1}{n^{3/2}}\Bigr)$

for some constant $c$ , and evaluate all terms at $n = 10^4$ (the constant is $c \approx -1.4604$ ).

Part III — Inversion: the equation $x\ln x = n$ .

Show that $x\ln x = n$ has exactly one solution $x_n \in \intco{1}{+\infty}$ for $n \geq 1$ , that $x_n \to \infty$ , and that $\ln x_n \sim \ln n$ .
Deduce the one-term inversion $x_n \sim \dfrac{n}{\ln n}$ , then bootstrap once more:

$\ln x_n = \ln n - \ln\ln n + o(1), \qquad x_n = \frac{n}{\ln n}\Bigl(1 + \frac{\ln\ln n}{\ln n} + o\Bigl(\frac{\ln\ln n}{\ln n}\Bigr)\Bigr).$
Test at $n = 10^6$ : the true root is $x \approx 87\,848$ ; compare with the one-term ( $\approx 72\,382$ ) and two-term ( $\approx 86\,140$ ) values, and explain the slow gain (the expansion parameter is $\frac{\ln\ln n}{\ln n}$ , only $\approx 0.19$ at $n = 10^6$ ).
We now admit the prime number theorem: the number $\pi(x)$ of primes $\leq x$ satisfies $\pi(x) \sim \frac{x}{\ln x}$ as $x \to \infty$ (proved honestly in the Year 3 volume). Writing $p_n$ for the $n$ -th prime, justify $\pi(p_n) = n$ , and run the inversion of questions 11–12 to prove

$p_n \sim n \ln n .$
Dividends: (a) show $\sum_{k \leq n} p_k \sim \frac{n^2\ln n}{2}$ (compare $\sum k\ln k$ with $\int t\ln t\,\dd t$ ); (b) compute the approximate chance that a uniformly random integer with $100$ digits is prime ( $\ln 10^{100} \approx 230.26$ : about one in $230$ ).

Part IV — The method exported: $x\tan x = 1$ .

Show that for each $n \geq 1$ the equation $\tan x = \frac1x$ has exactly one solution $x_n$ in $\intoo{n\pi}{\,n\pi + \frac\pi2}$ , and that $z_n = x_n - n\pi \to 0^+$ .
One term: $z_n \sim \dfrac{1}{n\pi}$ .
Show that the expansion of $z_n$ has no $\frac{c}{n^2}$ term: $z_n = \frac1{n\pi} + O\bigl(\frac{1}{n^3}\bigr)$ .
Three terms: using $\arctan u = u - \frac{u^3}3 + O(u^5)$ and $\frac1{x_n} = \frac{1}{n\pi} - \frac{z_n}{(n\pi)^2} + O(n^{-3}\cdot z_n^2)$ , prove

$x_n = n\pi + \frac{1}{n\pi} - \frac{4}{3\pi^3 n^3} + o\Bigl(\frac{1}{n^3}\Bigr).$
Check at $n = 3$ : true root $x_3 \approx 9.5293344$ ; compare the one- and three-term values, and contrast in one sentence with the course’s $\tan x = x$ (Example 6.23): where each sequence sits in its window, and why.

Part V — A dynamical bootstrap, rules of the game, synthesis.

Let $u_0 \in \intoo{0}{\pi}$ and $u_{n+1} = \sin u_n$ . Show $u_n \to 0$ decreasingly, and compute the limit of $\dfrac{1}{u_{n+1}^2} - \dfrac{1}{u_n^2}$ (expand $\sin^{-2}$ via $\sin u = u - \frac{u^3}6 + o(u^3)$ ).
Deduce, via Cesàro means (Year 1 volume), the classic

$u_n \sim \sqrt{\frac{3}{n}} .$
(Certified numerics) Using question 7’s rigorous bound, show that evaluating $\ln n + \gamma + \frac1{2n}$ at $n = 10^6$ yields $H_{10^6}$ with error at most $1.25\cdot10^{-13}$ — a million-term sum computed to thirteen digits by three terms.
(Rules of the game) Prove or refute, with proofs or counterexamples: (a) if $u_n \sim v_n \to +\infty$ then $\ln u_n \sim \ln v_n$ ; (b) if $u_n \sim v_n$ then $\eu^{u_n} \sim \eu^{v_n}$ ; (c) if $f \sim g$ at $+\infty$ ( $f, g$ differentiable) then $f' \sim g'$ .
(Synthesis) In one sentence each: the bootstrap loop of Method 6.22 as used in Parts I, III, IV; what the trapezoid correction adds to Theorem 6.6; why inversion of $x\ln x$ is exactly the bridge from $\pi(x)$ to $p_n$ ; and which of question 24’s rules protected which step. Name the two summits: the Euler–Maclaurin formula (first order), and the asymptotic law of the $n$ -th prime.

Solution

Solution of Problem 6.1.

1. Subtracting the two expansions: $\sum_i (c_i - c_i')\varphi_i = o(\varphi_k)$ . If some coefficient differs, let $i_0$ be the first: dividing by $\varphi_{i_0}$ and using $\varphi_j = o(\varphi_{i_0})$ for $j > i_0$ gives $c_{i_0} - c_{i_0}' = o(1)$ : zero, contradiction. For the expansion: with $u = \frac{\ln x}x \to 0$ ,

\frac{1}{x - \ln x} = \frac1x\cdot\frac{1}{1 - u} = \frac1x\bigl(1 + u + u^2 + O(u^3)\bigr) = \frac1x + \frac{\ln x}{x^2} + \frac{(\ln x)^2}{x^3} + o\Bigl(\frac{(\ln x)^2}{x^3}\Bigr).

No $\frac c{x^2}$ term appears because the expansion is a geometric series in $u = \frac{\ln x}{x}$ : every term carries as many powers of $\ln x$ as of $\frac1x$ beyond the first; the scale rung $\frac1{x^2}$ (coefficient of $(\ln x)^0$ ) is simply absent, with coefficient $0$ .

2. $f(x) = \eu^x + x$ is continuous, strictly increasing, with limits $-\infty$ and $+\infty$ : a bijection $\R \to \R$ , so $x_n = f^{-1}(n)$ exists and is unique, and $x_n \to +\infty$ ( $f^{-1}$ increases to $+\infty$ ). From $\eu^{x_n} = n - x_n$ : $x_n = \ln(n - x_n) \leq \ln n$ , so $x_n/n \to 0$ and $x_n = \ln n + \ln(1 - x_n/n) = \ln n + o(1) \sim \ln n$ .

3. Write $u_n = x_n/n$ . Second pass: $u_n = \frac{\ln n + o(1)}{n}$ , so

x_n = \ln n + \ln(1 - u_n) = \ln n - u_n + O(u_n^2) = \ln n - \frac{\ln n}{n} + o\Bigl(\frac{\ln n}n\Bigr).

Third pass: now $u_n = \frac{\ln n}{n} - \frac{\ln n}{n^2} + o\bigl(\frac{\ln n}{n^2}\bigr)$ , and $\ln(1 - u_n) = -u_n - \frac{u_n^2}2 + O(u_n^3)$ :

x_n = \ln n - \frac{\ln n}n + \frac{\ln n}{n^2} - \frac{(\ln n)^2}{2n^2} + o\Bigl(\frac{(\ln n)^2}{n^2}\Bigr) = \ln n - \frac{\ln n}{n} - \frac{(\ln n)^2}{2n^2} + o\Bigl(\frac{(\ln n)^2}{n^2}\Bigr),

the term $\frac{\ln n}{n^2}$ being absorbed into $o\bigl(\frac{(\ln n)^2}{n^2}\bigr)$ .

4. At $n = 1000$ : $\ln 1000 \approx 6.90776$ (error $7\cdot10^{-3}$ ); two terms: $6.90085$ (error $2\cdot10^{-5}$ ); three terms: $6.90082$ (error below $10^{-5}$ ), against $x_{1000} \approx 6.90083$ . Each pass buys roughly the predicted factor $\frac{\ln n}{n}$ .

5. Two integrations by parts, starting from the right: with $\frac{\dd}{\dd t}\bigl[\tfrac12t(1-t)\bigr] = \tfrac12 - t$ and $t(1-t)$ vanishing at both ends,

\frac12\int_0^1 t(1-t)g''(t)\dd t = -\int_0^1\Bigl(\frac12 - t\Bigr)g'(t)\dd t = -\Bigl[\Bigl(\frac12 - t\Bigr)g\Bigr]_0^1 - \int_0^1 g = \frac{g(0) + g(1)}2 - \int_0^1 g .

Rearranged, this is the stated identity.

6. Compute the increment, then apply question 5 to $g(t) = f(n + t)$ :

\begin{align*} E_{n+1} - E_n &= f(n{+}1) - \int_n^{n+1}\!f - \frac{f(n{+}1) - f(n)}2 \\ &= \frac{f(n) + f(n{+}1)}2 - \int_n^{n+1}\!f = \frac12\int_0^1 t(1-t)f''(n+t)\dd t . \end{align*}

Since $0 \leq t(1-t) \leq \frac14$ : $\abs{E_{n+1} - E_n} \leq \frac18\int_n^{n+1}\abs{f''}$ , whose sum over $n$ converges by hypothesis: $(E_n)$ converges (absolutely summable increments) to some $E$ , with

\abs{E - E_n} \leq \sum_{k\geq n}\abs{E_{k+1} - E_k} \leq \frac18\int_n^\infty\abs{f''} .

7. $f(t) = \frac1t$ : $f''(t) = \frac2{t^3}$ , $\int_1^\infty\abs{f''} = 1 < \infty$ . Question 6:

H_n = \ln n + \frac{1 + \frac1n}{2} + E + (E_n - E) = \ln n + \Bigl(E + \frac12\Bigr) + \frac1{2n} + \varepsilon_n,

with $\abs{\varepsilon_n} = \abs{E_n - E} \leq \frac18\int_n^\infty\frac{2\dd t}{t^3} = \frac1{8n^2}$ . Comparing with $H_n = \ln n + \gamma + o(1)$ (Example 6.7) identifies $E + \frac12 = \gamma$ .

8. From question 6’s increment formula,

\varepsilon_n = E_n - E = -\sum_{k\geq n}\frac12\int_0^1 t(1-t)\,\frac{2\,\dd t}{(k+t)^3} = -\sum_{k \geq n}\Bigl(\frac1{k^3}\int_0^1t(1-t)\dd t + O\Bigl(\frac1{k^4}\Bigr)\Bigr),

using $\frac{1}{(k+t)^3} = \frac1{k^3} + O\bigl(\frac1{k^4}\bigr)$ uniformly for $t \in \intcc01$ . With $\int_0^1 t(1-t) = \frac16$ and $\sum_{k\geq n}\frac1{k^3} \sim \frac{1}{2n^2}$ (Theorem 6.6):

\varepsilon_n = -\frac16\cdot\frac{1}{2n^2} + o\Bigl(\frac1{n^2}\Bigr) = -\frac{1}{12n^2} + o\Bigl(\frac{1}{n^2}\Bigr).

9. $f = \ln$ : $f''(t) = -\frac1{t^2}$ , absolutely integrable. Question 6 gives

\ln n! = \int_1^n\ln t\,\dd t + \frac{\ln n}2 + E + O\Bigl( \frac1{8}\int_n^\infty\frac{\dd t}{t^2}\Bigr) = \Bigl(n + \frac12\Bigr)\ln n - n + 1 + E + O\Bigl(\frac1n\Bigr),

so $d_n = 1 + E + O\bigl(\frac1n\bigr)$ : convergence of $(d_n)$ — Step 1 of Theorem 6.13 — plus the rate $O(1/n)$ . (Stirling’s value of the limit gives $E = \ln\sqrt{2\pi} - 1$ .)

10. $f(t) = t^{-1/2}$ : $f''(t) = \frac34 t^{-5/2}$ , absolutely integrable. Question 6:

\sum_{k=1}^n \frac1{\sqrt k} = 2\sqrt n - 2 + \frac{1 + \frac1{\sqrt n}}2 + E + O\bigl(n^{-3/2}\bigr) = 2\sqrt n + c + \frac{1}{2\sqrt n} + O\bigl(n^{-3/2}\bigr),

with $c = E - \frac32$ . At $n = 10^4$ : $2\sqrt n = 200$ , $c \approx -1.46035$ , $\frac1{2\sqrt n} = 0.005$ : predicted $198.54465$ , and indeed $\sum_{k\leq10^4}k^{-1/2} = 198.544645\dots$ — three terms, seven digits.

11. $t \mapsto t\ln t$ is continuous and strictly increasing on $\intco1\infty$ (derivative $\ln t + 1 \geq 1$ ), from $0$ to $+\infty$ : a unique $x_n$ exists, and $x_n \to \infty$ (else $x_n\ln x_n$ would stay bounded). Taking logarithms in $x_n\ln x_n = n$ : $\ln x_n + \ln\ln x_n = \ln n$ ; since $\ln\ln x_n = o(\ln x_n)$ , dividing by $\ln x_n$ gives $\frac{\ln n}{\ln x_n} \to 1$ : $\ln x_n \sim \ln n$ .

12. From $x_n = \frac{n}{\ln x_n}$ and $\ln x_n \sim \ln n$ : $x_n \sim \frac{n}{\ln n}$ . Next pass: $\ln\ln x_n = \ln\bigl(\ln n\,(1 + o(1))\bigr) = \ln\ln n + o(1)$ , so $\ln x_n = \ln n - \ln\ln n + o(1)$ and

x_n = \frac{n}{\ln n - \ln\ln n + o(1)} = \frac{n}{\ln n}\cdot\frac{1}{1 - \frac{\ln\ln n + o(1)}{\ln n}} = \frac{n}{\ln n}\Bigl(1 + \frac{\ln\ln n}{\ln n} + o\Bigl(\frac{\ln\ln n}{\ln n}\Bigr)\Bigr).

13. At $n = 10^6$ : $\frac{n}{\ln n} \approx 72\,382$ (off by $18\%$ ), two terms give $\approx 86\,140$ (off by $1.9\%$ ), against the true $x \approx 87\,848$ . The gain per pass is only the factor $\frac{\ln\ln n}{\ln n} \approx \frac{2.63}{13.8} \approx 0.19$ : logarithmic scales converge with maddening slowness — a fact of life wherever primes are involved.

14. There are exactly $n$ primes $\leq p_n$ (namely $p_1, \dots, p_n$ ): $\pi(p_n) = n$ . The prime number theorem (admitted; Year 3 volume) gives $n = \pi(p_n) \sim \frac{p_n}{\ln p_n}$ , i.e. $p_n \sim n\ln p_n$ : this is the equation $x\ln x \approx n$ read backwards. Taking logarithms: $\ln p_n = \ln n + \ln\ln p_n + o(1)$ , and $\ln\ln p_n = o(\ln p_n)$ forces $\ln p_n \sim \ln n$ as in question 11. Substituting back:

p_n \sim n\ln p_n = n\,\ln n\,\frac{\ln p_n}{\ln n} \sim n\ln n .

15. (a) Fix $\varepsilon > 0$ ; for $k$ large, $(1 - \varepsilon)k\ln k \leq p_k \leq (1 + \varepsilon)k\ln k$ . By comparison with the increasing $t\ln t$ (Theorem 6.6-type bracketing), $\sum_{k\leq n}k\ln k = \int_1^n t\ln t\,\dd t + O(n\ln n) = \frac{n^2\ln n}2 - \frac{n^2}4 + O(n\ln n) \sim \frac{n^2\ln n}2$ . Hence $\sum_{k\leq n}p_k = \frac{n^2\ln n}{2}(1 + O(\varepsilon) + o(1))$ for every $\varepsilon$ : $\sum_{k\leq n}p_k \sim \frac{n^2\ln n}2$ . (b) By the prime number theorem, among the integers up to $10^{100}$ a proportion $\sim \frac{1}{\ln 10^{100}} = \frac1{230.26\dots}$ are prime: a uniformly random $100$ -digit integer is prime with probability about $\frac1{230}$ .

16. On $\intoo{n\pi}{n\pi + \frac\pi2}$ , $g(x) = \tan x - \frac1x$ is continuous and strictly increasing ( $g' = 1 + \tan^2x + \frac1{x^2} > 0$ ), with $g \to -\frac1{n\pi} < 0$ at the left end and $g \to +\infty$ at the right: exactly one root $x_n$ . Since $\tan z_n = \tan x_n = \frac1{x_n} \to 0$ with $z_n \in \intoo{0}{\frac\pi2}$ : $z_n \to 0^+$ .

17. $\tan z_n \sim z_n$ and $\frac1{x_n} \sim \frac1{n\pi}$ : $z_n \sim \frac1{n\pi}$ .

18. $z_n = \arctan\frac1{x_n}$ and $\arctan u = u + O(u^3)$ . With $z_n = O(\frac1n)$ :

\frac1{x_n} = \frac{1}{n\pi}\cdot\frac1{1 + \frac{z_n}{n\pi}} = \frac1{n\pi} - \frac{z_n}{n^2\pi^2} + O\Bigl(\frac1{n^4}\Bigr) = \frac1{n\pi} + O\Bigl(\frac1{n^3}\Bigr),

so $z_n = \frac1{n\pi} + O\bigl(\frac1{n^3}\bigr)$ : the $\frac{c}{n^2}$ rung carries coefficient $0$ , because the first correction to $\frac1{x_n}$ is itself of size $\frac{z_n}{n^2} = O(n^{-3})$ .

19. Insert $z_n = \frac1{n\pi} + O(n^{-3})$ into the previous display:

\frac{1}{x_n} = \frac{1}{n\pi} - \frac{1}{n^3\pi^3} + O\Bigl(\frac1{n^5}\Bigr),

then $z_n = \arctan\frac1{x_n} = \frac1{x_n} - \frac{1}{3}\Bigl(\frac1{x_n}\Bigr)^3 + O\Bigl(\frac1{n^5}\Bigr) = \frac1{n\pi} - \frac{1}{n^3\pi^3} - \frac{1}{3n^3\pi^3} + O\Bigl(\frac1{n^5}\Bigr)$ :

x_n = n\pi + \frac{1}{n\pi} - \frac{4}{3\pi^3n^3} + O\Bigl(\frac1{n^5}\Bigr).

20. At $n = 3$ : one term $9.53088$ , three terms $9.52929$ , true root $9.52933$ : errors $1.5\cdot10^{-3}$ and $5\cdot10^{-5}$ . Contrast: for $\tan x = x$ the root must make $\tan$ huge, so it hugs the right end $n\pi + \frac\pi2$ of the window, at distance $\sim\frac1{n\pi}$ before the asymptote; for $x\tan x = 1$ the root must make $\tan$ tiny, so it sits just past the left end $n\pi$ , at distance $\sim\frac1{n\pi}$ after the zero. Same method, mirror geography.

21. $\sin u < u$ on $\intoo0\pi$ and $\sin$ maps $\intoo0\pi$ into $\intoc01 \subseteq \intoo0\pi$ : after one step $u_1 \in \intoc{0}{1}$ , then $(u_n)$ decreases and is bounded below by $0$ : it converges to a fixed point of $\sin$ , i.e. to $0$ . Expansion: $\sin u = u(1 - \frac{u^2}6 + o(u^2))$ , so

\frac{1}{u_{n+1}^2} - \frac1{u_n^2} = \frac{1}{u_n^2}\Bigl(\bigl(1 - \tfrac{u_n^2}6 + o(u_n^2)\bigr)^{-2} - 1\Bigr) = \frac{1}{u_n^2}\Bigl(\frac{u_n^2}{3} + o(u_n^2)\Bigr) \longrightarrow \frac13 .

22. By Cesàro (Year 1 volume), the mean of the increments converges to the same limit:

\frac{1}{n}\cdot\frac{1}{u_n^2} = \frac1n\Bigl(\frac1{u_0^2} + \sum_{k=0}^{n-1} \Bigl(\frac1{u_{k+1}^2} - \frac1{u_k^2}\Bigr)\Bigr) \longrightarrow \frac13 ,

so $u_n^2 \sim \frac3n$ and, all terms being positive, $u_n \sim \sqrt{3/n}$ .

23. By question 7, $\abs{H_n - \ln n - \gamma - \frac1{2n}} \leq \frac1{8n^2}$ . At $n = 10^6$ this bound is $\frac{1}{8\cdot10^{12}} = 1.25\cdot10^{-13}$ : three computed terms deliver the million-term harmonic sum to thirteen digits, with a fully rigorous error certificate — the whole point of an asymptotic formula with explicit remainder.

24. (a) True: $\ln u_n - \ln v_n = \ln\frac{u_n}{v_n} \to 0$ while $\ln v_n \to +\infty$ , so the ratio of logarithms tends to $1$ . (b) False: $u_n = n + 1 \sim v_n = n$ , but $\eu^{u_n}/\eu^{v_n} = \eu \neq 1$ . Equivalence tolerates additive errors $o(1)$ in the exponent, not $O(1)$ . (c) False: $f(x) = x + \sin(x^2) \sim g(x) = x$ at $+\infty$ , but $f'(x) = 1 + 2x\cos(x^2)$ oscillates unboundedly while $g' = 1$ : derivatives of equivalent functions need not be comparable at all.

25. The loop of Method 6.22 ran identically three times: localize the root, extract a crude term, feed it back for the next order — on $\eu^x + x = n$ (Part I), on $x\ln x = n$ (Part III), on $x\tan x = 1$ (Part IV). The trapezoid correction upgrades the series–integral comparison from “the difference converges” to an explicit $\frac{f(1) + f(n)}2$ term with a certified $O(\int_n^\infty \abs{f''})$ remainder — constants and error bars instead of mere convergence. The bridge to primes is pure inversion: the prime number theorem says $\pi(x)\ln x \approx x$ , so $p_n$ , defined by $\pi(p_n) = n$ , solves an $x\ln x = n$ equation — and inherits its asymptotics. Rule (a) of question 24 legitimized every passage from $u_n \sim v_n$ to $\ln u_n \sim \ln v_n$ (questions 11, 14); the falsity of (b) is why we never exponentiate equivalences. Summits: the Euler–Maclaurin formula to first order (question 6), and the asymptotic law $p_n \sim n\ln n$ of the $n$ -th prime (question 14).

Terms defined in this chapter

See all 395 terms in the glossary