Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

6Vergelijking van functies

De asymptotische analyse — de kunst om een ingewikkelde grootheid te vervangen door een eenvoudige plus een beheerste fout — begon in het volume van bachelorjaar 1 met taylorontwikkelingen. Dit hoofdstuk maakt er een vak op zich van: ontwikkelingen langs algemene schalen, de vergelijking van reeks en integraal met haar volle asymptotische kracht, de formule van Stirling (volledig bewezen), en de systematische studie van impliciet gedefinieerde rijen. Deze technieken zijn het dagelijks brood van de asymptotische analyse, en elk later hoofdstuk dat iets schat — reeksen, integralen, kansen — eet mee aan deze tafel.

6.1 Vergelijkingsrelaties en schalen

Definitie 6.1

Bij een punt $a$ ( $a \in \R$ of $\pm\infty$ ), voor functies (of voor rijen, met $n \to \infty$ ): $f = o(g)$ , $f = O(g)$ en $f \sim g$ als in het volume van bachelorjaar 1. Een vergelijkingsschaal bij $a$ is een familie positieve functies die paarsgewijs vergelijkbaar zijn en door $o(\cdot)$ totaal geordend worden — de standaardschaal bij $+\infty$ is

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

lexicografisch geordend naar $(\alpha, \beta)$ , en zo nodig verfijnd met exponentiëlen $\eu^{\gamma x}$ .

Definitie 6.2 (Asymptotische ontwikkeling)

$f$ heeft de asymptotische ontwikkeling

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 de schaal})

wanneer de opeenvolgende resttermen aan de aangegeven schattingen voldoen. De coëfficiënten liggen dan vast: $c_1 = \lim f/\varphi_1$ , en inductief $c_{i+1} = \lim\,(f - \sum_{j \leq i} c_j\varphi_j)/\varphi_{i+1}$ .

Voorbeeld 6.3

Taylorontwikkelingen zijn asymptotische ontwikkelingen langs de schaal $(x - a)^k$ bij $a$ . Maar het begrip is strikt ruimer: bij $+\infty$ geldt

\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),

een ontwikkeling langs de gemengde schaal — geen enkele stelling van Taylor is hier van toepassing, alleen de meetkundige ontwikkeling en het rekenen met $o$ ’s.

Voorbeeld 6.4 (De standaardschaal is werkelijk geordend)

De lexicografische bewering van Definitie 6.1 vraagt per geval één regel bewijs. Vergelijk $x^{\alpha}(\ln x)^{\beta}$ en $x^{\alpha'}(\ln x)^{\beta'}$ bij $+\infty$ . Is $\alpha < \alpha'$ , dan is de verhouding $x^{\alpha - \alpha'}(\ln x)^{\beta - \beta'} \to 0$ , want een negatieve macht van $x$ verplettert elke macht van $\ln x$ (zet $x = \eu^t$ : $\eu^{(\alpha - \alpha')t}\,t^{\beta - \beta'} \to 0$ volgens de limiet “exponentieel wint van polynomiaal” uit het volume van bachelorjaar 1). Is $\alpha = \alpha'$ en $\beta < \beta'$ , dan is de verhouding rechtstreeks $(\ln x)^{\beta - \beta'} \to 0$ . De lexicografisch geordende paren $(\alpha, \beta)$ ordenen de schaal dus naar $o(\cdot)$ — en de substitutie $x = \eu^t$ is de universele truc voor gemengde vergelijkingen van machten en logaritmen.

Voorbeeld 6.5 (Een menagerie rangschikken)

Schalen moeten geordend zijn; hier is de standaardoefening. Vergelijk bij $+\infty$ de grootheden $n^{10}$ , $\eu^{\sqrt{\ln n}\,\cdot\,\sqrt n}$ , $2^n$ en $n^{\ln n}$ door logaritmen te nemen:

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

waarbij $a_n \ll b_n$ betekent dat $a_n = o(b_n)$ ; de tweede term is $\ln(n^{\ln n})$ . Exponentiëren behoudt deze strikte kloven (gaat $\ln u_n - \ln v_n \to -\infty$ , dan $u_n/v_n \to 0$ ), dus

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) .

De moraal, tweemaal: vergelijk altijd via logaritmen (verschillen van logaritmen, niet verhoudingen van logaritmen), en besluit nooit tot $u_n \sim v_n$ uit $\ln u_n \sim \ln v_n$ — het paar $n^{10}$ en $n^{\ln n}$ heeft een $\ln$ -verhouding die naar $\infty$ gaat, terwijl $2^n$ en $4^n$ een $\ln$ -verhouding van precies $2$ hebben en toch wild niet-equivalent zijn.

6.2 Vergelijking van reeks en integraal, asymptotisch

Stelling 6.6

Zij $f$ continu, positief en dalend op $\intco{1}{+\infty}$ .

Convergeert $\int_1^{\infty} f$ , dan voldoen de restsommen aan

$\int_{n+1}^{\infty} f \;\leq\; \sum_{k > n} f(k) \;\leq\; \int_{n}^{\infty} f .$
Divergeert $\int_1^\infty f$ , dan voldoen de partiële sommen aan $\sum_{k=1}^{n} f(k) = \int_1^n f + C + o(1)$ voor zekere constante $C$ : het verschil $\sum_{k \leq n} f(k) - \int_1^n f$ convergeert.

Bewijs. De insluiting $f(k+1) \leq \int_k^{k+1} f \leq f(k)$ (dalend) was het middel uit bachelorjaar 1; sommeren over $k \geq n+1$ respectievelijk $k \geq n$ geeft (1). Zet voor (2) $u_k = f(k) - \int_k^{k+1} f$ : uit de insluiting volgt $0 \leq u_k \leq f(k) - f(k+1)$ , dus zijn de partiële sommen van $\sum u_k$ begrensd door de telescopische som $f(1) - f(n+1) \leq f(1)$ : de reeks convergeert. Bovendien is de rij $\bigl(\int_n^{n+1} f\bigr)_n$ niet-stijgend ( $f$ daalt) en niet-negatief, en dus convergent. Met

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

convergeert het rechterlid als $n \to \infty$ : het verschil convergeert naar een constante $C$ , en dat is uitspraak (2). ∎

Voorbeeld 6.7 (De harmonische ontwikkeling)

Voor $f(t) = \frac1t$ : $H_n = \ln n + \gamma + o(1)$ , waarmee de constante van Euler (volume van bachelorjaar 1) met een schoner bewijs wordt teruggevonden. Eén orde verder (Oefening 6.3):

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

Getallen maken de winst zichtbaar bij $n = 10$ : $H_{10} = 2.928968\dots$ en $\ln 10 = 2.302585\dots$ , dus de ruwe schatting van $\gamma$ is $H_{10} - \ln 10 = 0.626383$ , er $0.049$ naast; trekken we de correctie $\frac1{20}$ eraf, dan krijgen we $0.576383$ , slechts $8.3\cdot10^{-4}$ van $\gamma = 0.577216$ verwijderd — en dat is zelf de volgende term $\frac{1}{12\cdot100}$ van de ontwikkeling, zoals de weekendopgave bewijst (vraag 8).

Voorbeeld 6.8 (Een ruwe $\ln(n!)$ zonder Stirling)

Het insluitingsmiddel alleen lokaliseert $\ln(n!)$ al. Omdat $\ln$ stijgt, geldt

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

en sommeren over $k = 2, \dots, n$ (met $\int_1^n\ln = n\ln n - n + 1$ ) geeft

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

Beide hekken zijn $n\ln n - n + O(\ln n)$ : dus $\ln(n!) = n\ln n - n + O(\ln n)$ , en in het bijzonder $\ln(n!) \sim n\ln n$ . Wat Stirling daaraan toevoegt zijn de volgende twee sporten — de $\frac12\ln n$ en de constante $\ln\sqrt{2\pi}$ — die de fijnere telescopering van Stelling 6.13 kosten. Weten welke precisie elk gereedschap koopt, is de helft van het asymptotische vakmanschap.

Voorbeeld 6.9 (Wegvallen vraagt om ontwikkelingen)

Bereken de limiet van $\sqrt{n^2 + n} - n$ . Beide termen zijn $\sim n$ , en “ $\sim n - n$ ” is betekenisloos: equivalenten mogen niet worden afgetrokken. Ontwikkel in plaats daarvan:

\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(\frac{1}{n^2}\Bigr) :

de limiet is $\frac12$ , met de naderingssnelheid $\frac1{8n}$ als bonus. Het mechanisme verdient een naam: een verschil van twee grote equivalente grootheden leeft volledig in hun volgende termen, dus moet men ontwikkelen tot de eerste orde waarin de twee kanten verschillen — en de restterm meenemen om te certificeren dat er in die orde niets anders overleeft.

Voorbeeld 6.10 (Een divergente vergelijking, uitgewerkt)

Voor $f(t) = \frac{1}{t\ln t}$ op $\intco{2}{+\infty}$ (continu, positief, dalend) is $\int_2^x f = \ln\ln x - \ln\ln 2 \to \infty$ , dus geeft Stelling 6.6 (2)

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

voor zekere constante $C$ . Twee lessen. Ten eerste is de divergentie echt maar ijzig traag: de partiële som overschrijdt $4$ pas rond $n \approx \eu^{\eu^{4 - C}}$ , astronomisch groot. Ten tweede werd de vorm $\ln\ln n$ geleverd door een primitieve, niet geraden: voor monotone termen is de integraal het canonieke somgereedschap, en de constante $C$ — net als de $\gamma$ van Euler — is het geheugen van de eerste termen.

6.3 De formule van Stirling

Lemma 6.11 (Wallis-integralen, hernomen)

Zij $W_n = \int_0^{\pi/2} \sin^n t\,\dd t$ . Dan is $nW_nW_{n-1} = \frac\pi2$ voor $n \geq 1$ , daalt $(W_n)$ , en geldt $W_n \sim \sqrt{\dfrac{\pi}{2n}}$ .

Bewijs. Partiële integratie geeft $nW_n = (n-1)W_{n-2}$ ( $n \geq 2$ ), dus is $nW_nW_{n-1}$ constant in $n$ , gelijk aan $1 \cdot W_1 W_0 = \frac\pi2$ . Dalend: $\sin^{n+1} \leq \sin^n$ op $\intcc{0}{\frac\pi2}$ . De insluiting in detail: de monotonie geeft $W_{n+1} \leq W_n \leq W_{n-1}$ , en deling door $W_{n-1} > 0$ levert

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

waarbij de linkeridentiteit uit de recurrentie bij index $n + 1$ komt. Beide grenzen gaan naar $1$ : dus $W_n \sim W_{n-1}$ , waaruit

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

∎

Voorbeeld 6.12 (De eerste Wallis-integralen)

Uit $W_0 = \frac\pi2$ , $W_1 = 1$ en de recurrentie $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}.

De even indices dragen een $\pi$ , de oneven zijn rationaal — de twee vervlochten producten uit de gesloten vormen. Numeriek is $W_6 \approx 0.4909$ tegenover de asymptotische waarde $\sqrt{\pi/12} \approx 0.5116$ : bij $n = 6$ zit het equivalent al binnen $5\%$ , en de productidentiteit klopt exact bij elke $n$ : $6\,W_6W_5 = 6\cdot\frac{5\pi}{32}\cdot\frac8{15} = \frac\pi2$ . Kleine tabellen als deze zijn de goedkoopste manier om een algebrafoutje te vangen voordat het een asymptotisch argument besmet.

Stelling 6.13 (Stirling)

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

Bewijs. Stap 1: $n! \sim C \sqrt n\, (n/\eu)^n$ voor zekere constante $C > 0$ . Zet

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

Dan is

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),

volgens de taylorontwikkeling van $\ln(1 + \frac1n)$ . De reeks $\sum (d_n - d_{n+1})$ convergeert dus absoluut (vergelijking met $\sum n^{-2}$ ), zodat $(d_n)$ convergeert, zeg naar $d$ ; exponentiëren geeft $n! \sim C\sqrt n\,(n/\eu)^n$ met $C = \eu^{d}$ .

Stap 2: $C = \sqrt{2\pi}$ via Wallis. De gesloten vorm $W_{2p} = \frac{(2p)!}{4^p (p!)^2}\cdot\frac\pi2$ (uit de recurrentie, de berekening uit bachelorjaar 1 opnieuw gedaan in de context van Lemma 6.11) combineert met stap 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}} .

Vergelijking met $W_{2p} \sim \sqrt{\frac{\pi}{4p}}$ (Lemma 6.11): uit $\frac{\pi}{C\sqrt{2p}} = \sqrt{\frac{\pi}{4p}}\,(1 + o(1))$ volgt $C = \pi \sqrt{\frac{4p}{2p\,\pi}} = \sqrt{2\pi}$ . ∎

Voorbeeld 6.14 (Centrale binomiaalcoëfficiënt)

\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}} :

de kans dat een symmetrische toevalswandeling op tijdstip $2n$ naar $0$ terugkeert, is $\sim \frac{1}{\sqrt{\pi n}}$ — een aankondiging van Hoofdstuk 22.

Opmerking 6.15 (Vooruitblik binnen dit volume)

Elk kwantitatief hoofdstuk hierna spreekt de taal van dit hoofdstuk. Hoofdstuk 7 klasseert reeksen door de termen met de schaal $n^{-\alpha}(\ln n)^{-\beta}$ te vergelijken — de weekendopgave daar brengt die grens volledig in kaart. Hoofdstuk 9 doet hetzelfde voor oneigenlijke integralen, met dezelfde schaal in de continue veranderlijke. Hoofdstuk 11 berekent convergentiestralen uit $\limsup\abs{a_n}^{1/n}$ , een oefening in equivalenten van $n$ -de wortels waarbij Stirling de standaardsleutel is ( $\sqrt[n]{n!} \sim \frac n\eu$ , Oefening 6.4). En de kanshoofdstukken verzilveren Stirling rechtstreeks: de lokale schattingen van Hoofdstuk 22 voor binomiaalcoëfficiënten zijn woordelijk Voorbeeld 6.14 en Voorbeeld 6.21. De asymptotiek is hier geen hoofdstuk; zij is het accent van het hele volume.

Methode 6.16 (De checklist voor bootstrappen)

Controleer vier punten voordat je een gebootstrapte ontwikkeling vertrouwt. (1) Eerst het bestaan: het nulpunt of de rij moet zijn vastgepind (monotonie, tussenwaarden) voordat er ook maar iets wordt ontwikkeld — symbolen zonder referent laten zich prachtig ontwikkelen en betekenen niets. (2) Eén orde per ronde: elke substitutie mag slechts tot de orde van de ingevoerde schatting worden vertrouwd; twee nieuwe termen uit één ronde persen is de klassieke bron van verkeerde coëfficiënten. (3) Resttermen rijden mee: sleep de $o(\cdot)$ door elke algebraïsche stap mee en laat de absorptie (kleinere termen door grotere resttermen opgeslokt) pas aan het eind gebeuren, en expliciet. (4) Numerieke controle: evalueer bij één eerlijke waarde van $n$ ; een fout in een coëfficiënt overleeft een algebraïsche herafleiding verrassend vaak, en overleeft de rekenkunde bijna nooit.

Opmerking 6.17 (Klassieke valkuilen)

(i) Equivalenten tellen slecht op: uit $u_n \sim n + \ln n$ en $v_n \sim -n$ mag men niet besluiten dat $u_n + v_n \sim \ln n$ ; wegvallende termen vragen om ontwikkelingen met expliciete resttermen, nooit om kale equivalenten. (ii) Exponentieer nooit een equivalentie: $n + 1 \sim n$ maar $\eu^{n+1} \not\sim \eu^n$ ; de veilige richting is logaritmen nemen van equivalenten die naar $+\infty$ gaan (de weekendopgave van dit hoofdstuk, vraag 24). (iii) Een asymptotische ontwikkeling hoort bij een schaal: schrijven dat $f = \frac1x + o\bigl(\frac1{x^2}\bigr)$ beweert meer dan $f = \frac1x + o\bigl(\frac1x\bigr)$ , en de twee mengen maakt alle latere algebra ongeldig. (iv) Substitueer bij het bootstrappen de hele huidige ontwikkeling, restterm inbegrepen — een $o(\cdot)$ halverwege laten vallen levert plausibele maar verkeerde coëfficiënten op. (v) De vergelijking van reeks en integraal heeft monotonie nodig: voor oscillerende termen faalt zij ronduit (vergelijk $\sum\frac{\sin k}k$ , Hoofdstuk 7).

Voorbeeld 6.18 (Stirling in getallen)

Bij $n = 10$ geeft de formule $\sqrt{20\pi}\,(10/\eu)^{10} \approx 3\,598\,696$ tegenover $10! = 3\,628\,800$ : een relatieve fout van $8.3\cdot10^{-3}$ , opmerkelijk voor een “asymptotische” uitspraak bij $n = 10$ . De fout heeft structuur — de exacte verfijning $n! = \sqrt{2\pi n}\,(n/\eu)^n\bigl(1 + \frac1{12n} + O(n^{-2})\bigr)$ — en haar eerste correctie $\frac1{120} \approx 8.3\cdot10^{-3}$ verklaart de waargenomen kloof vrijwel precies. Het gereedschap van Euler–Maclaurin uit de weekendopgave is juist de systematische bron van zulke correctietermen.

Opmerking 6.19 (Waar dit hoofdstuk wordt gebruikt)

De asymptotische vergelijking is de grammatica van alles wat verderop kwantitatief is: de convergentietests en het Bertrand-panorama van Hoofdstuk 7, de integreerbaarheidscriteria van Hoofdstuk 9, de berekeningen van convergentiestralen in Hoofdstuk 11, en de limietstellingen van Hoofdstuk 22 (waar Stirling de schattingen van de Moivre en Laplace aandrijft). Het volume van bachelorjaar 3 industrialiseert het ene idee dat wij hier met de hand bewijzen — haal de hoofdterm eruit, begrens de rest — tot de methode van Laplace en de gedomineerde convergentie.

Voorbeeld 6.20 (Een integraal met zichzelf vergeleken: $\int_2^x \frac{\dd t}{\ln t}$ )

De vergelijkingsgereedschapskist werkt ook op integralen. Zij $F(x) = \int_2^x\frac{\dd t}{\ln t}$ (de integrand is continu op $\intco2\infty$ ). Partieel integreren:

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),

en de restintegraal is $o\bigl(\frac{x}{\ln x}\bigr)$ : splits haar bij $\sqrt x$ en begrens met

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

Bijgevolg is $F(x) \sim \frac{x}{\ln x}$ . Wie de priemgetalstelling in de weekendopgave van dit hoofdstuk is tegengekomen, herkent $F$ : het is de logaritmische integraal, de betere schatter van $\pi(x)$ , en de berekening laat zien dat zij tot op de eerste orde met $\frac{x}{\ln x}$ overeenstemt.

Voorbeeld 6.21 (Stirling op een scheve binomiaalcoëfficiënt)

Dezelfde routine met drie faculteiten als bij Voorbeeld 6.14 geeft voor $\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} .

De exponentiële snelheid $\frac{27}4 = \frac{3^3}{2^2}$ is $\eu^{3n\,H(1/3)}$ in de entropienotatie van de informatietheorie: scheve binomiaalcoëfficiënten groeien strikt langzamer dan de centrale $4^n$ per twee stappen — hier $(27/4)^{1/3} \approx 1.89 < 2$ per stap. Elke asymptotiek van binomiaalcoëfficiënten in de combinatoriek en de kansrekening (Hoofdstuk 22) is deze ene berekening met andere gewichten.

6.4 Impliciet gedefinieerde rijen

Methode 6.22

Om de asymptotiek van de oplossingen $x_n$ van een vergelijking $F(x, n) = 0$ te vinden:

Lokaliseer: bewijs het bestaan en de eenduidigheid van $x_n$ in een bepaald interval (monotonie, tussenwaardestelling), en bepaal het ruwe gedrag (limiet, groeiorde).
Bootstrap: substitueer de ruwe vorm $x_n = (\text{hoofdterm})(1 + \varepsilon_n)$ in de vergelijking en los op naar de volgende orde van $\varepsilon_n$ ; herhaal, waarbij elke ronde één orde verfijnt.

Voorbeeld 6.23

Voor $n \geq 1$ heeft de vergelijking $\tan x = x$ precies één oplossing $x_n$ in $\intoo{n\pi - \frac\pi2}{n\pi + \frac\pi2}$ (de functie $\tan x - x$ stijgt daar van $-\infty$ tot $+\infty$ , want haar afgeleide is $\tan^2 x \geq 0$ ). Ruw: $x_n = n\pi + \frac\pi2 - y_n$ met $y_n \in \intoo{0}{\pi}$ ; omdat $x_n \to \infty$ en $\tan x_n = x_n \to +\infty$ , nadert $x_n$ de asymptoot van links: $y_n \to 0$ . Bootstrap: $\tan x_n = \cot y_n = \frac{1}{\tan y_n} \sim \frac{1}{y_n}$ , en de vergelijking $\cot y_n = x_n \sim n\pi$ geeft $y_n \sim \frac{1}{n\pi}$ . Bijgevolg is

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

en het proces gaat tot elke orde door (Oefening 6.6).

Voorbeeld 6.24 (Een tweede ronde van de methode)

Los $x + \ln x = n$ asymptotisch op. Lokaliseer: $x \mapsto x + \ln x$ stijgt op $\intoo{0}{+\infty}$ van $-\infty$ tot $+\infty$ : dus één nulpunt $x_n$ , en $x_n \to \infty$ . Ruw: uit $\ln x_n = o(x_n)$ volgt $x_n \sim n$ . Bootstrap: uit $x_n = n - \ln x_n$ en $\ln x_n = \ln n + o(1)$ (logaritmen van equivalenten, beide leden $\to \infty$ ):

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

nog een ronde, met $\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).

(Controle bij $n = 100$ : het nulpunt is $x \approx 95.4415$ ; de formule met drie termen geeft $100 - 4.6052 + 0.0461 = 95.4409$ en die met twee termen $95.3948$ — elke ronde wint de voorspelde orde.) Dezelfde lus, een derde landschap: de methode van Methode 6.22 maalt niet om de gedaante van de vergelijking, zolang elke ronde de dominante onbekende isoleert.

6.5 Oefeningen

Oefening 6.1 ★

Ontwikkel bij $+\infty$ , twee termen voorbij de hoofdterm:

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

Oplossing

Oplossing van Oefening 6.1.

$\sqrt{x^2 + x + 1} = x\sqrt{1 + \tfrac1x + \tfrac{1}{x^2}} = x + \frac12 + \frac38\cdot\frac1x + o\bigl(\frac1x\bigr)$ (binomiale ontwikkeling: $\frac12 u - \frac18 u^2$ met $u = \frac1x + \frac{1}{x^2}$ geeft $\frac{1}{2x} + \frac{1}{2x^2} - \frac{1}{8x^2} = \frac{1}{2x} + \frac{3}{8x^2}$ , en vermenigvuldig daarna met $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)$ .

Derde functie: ontwikkel elke 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).

Orden de bijdragen op de schaal bij $+\infty$ : $\frac{\ln x}{x} \gg \frac{1}{x} \geq \bigl|\frac{\sin x}{x}\bigr| \gg \frac{(\ln x)^2}{x^2}$ . De twee termen na de hoofdterm $1$ zijn dus $\frac{\ln x}{x}$ , en daarna de begrensd oscillerende 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).

Oefening 6.2 ★

Geef de aard (convergentie of divergentie) en, bij divergentie, de hoofdasymptotiek van $\sum_{k \leq n} k^\alpha$ voor $\alpha > -1$ , $\alpha = -1$ en $\alpha < -1$ , met Stelling 6.6.

Oplossing

Oplossing van Oefening 6.2.

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

$\alpha > -1$ : divergentie, en volgens Stelling 6.6 (2) geldt $\sum_{k\leq n} k^\alpha = \frac{n^{\alpha+1}}{\alpha+1} + C + o(1)$ als $\alpha < 0$ (daar daalt $f$ ); voor $\alpha \geq 0$ ( $f$ stijgt) geeft dezelfde insluiting met omgekeerde ongelijkheden $\sum_{k \leq n} k^\alpha \sim \frac{n^{\alpha + 1}}{\alpha + 1}$ .

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

$\alpha < -1$ : convergentie, met restsom $\sum_{k > n} k^\alpha \sim \frac{n^{\alpha+1}}{-(\alpha+1)}$ volgens de insluiting (1) (beide integraalgrenzen zijn met die waarde equivalent).

Oefening 6.3 ★★

Bewijs dat $H_n = \ln n + \gamma + \frac{1}{2n} + o\bigl(\frac1n\bigr)$ . (Bestudeer $v_n = H_n - \ln n - \gamma$ : toon aan dat $v_n - v_{n+1} = \frac{1}{2n^2} + O(n^{-3})$ en sommeer de staart, met de vergelijking $\sum_{k \geq n} \frac{1}{2k^2} \sim \frac{1}{2n}$ — Stelling 6.6 (1).)

Oplossing

Oplossing van Oefening 6.3.

Zij $v_n = H_n - \ln n - \gamma \to 0$ . Dan is

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),

met $\frac{1}{n+1} = \frac1n - \frac{1}{n^2} + O(n^{-3})$ . Omdat $v_n \to 0$ , geeft het telescoperen van de staart

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),

via Stelling 6.6 (1) toegepast op $t^{-2}$ (restsom $\sim \frac1n$ , gehalveerd) en op $t^{-3}$ . Bijgevolg is $H_n = \ln n + \gamma + \frac{1}{2n} + o(\frac1n)$ .

Oefening 6.4 ★★

Bepaal met Stirling equivalenten van $\dfrac{(3n)!}{(n!)^3}$ , $\;\dfrac{n!}{n^n}$ en $\;\sqrt[n]{n!}$ (als $\frac n\eu(1 + o(1))$ , tot op twee termen preciesgemaakt).

Oplossing

Oplossing van Oefening 6.4.

Drie keer Stirling:

\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} .

(Zorgvuldig: $\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)$ met $\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).

Oefening 6.5 ★★

Bewijs voor $n \geq 2$ dat $x^n + x = 1$ precies één oplossing $x_n \in \intoo{0}{1}$ heeft, dat $x_n \to 1$ , en leid af dat

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

(Uit $x_n^n = 1 - x_n$ : neem logaritmen en bootstrap met $x_n = 1 - \varepsilon_n$ .)

Oplossing

Oplossing van Oefening 6.5.

$g(x) = x^n + x - 1$ stijgt strikt op $\intcc{0}{1}$ van $-1$ naar $1$ : dus één nulpunt $x_n$ . Omdat $x_n^n = 1 - x_n \in \intoo{0}{1}$ : zou $x_n \leq c < 1$ langs een deelrij, dan $x_n^n \leq c^n \to 0$ , dus $1 - x_n \to 0$ : in strijd met $x_n \leq c$ . Bijgevolg is $x_n \to 1$ .

Schrijf $x_n = 1 - \varepsilon_n$ met $\varepsilon_n \to 0^+$ . De vergelijking luidt $(1 - \varepsilon_n)^n = \varepsilon_n$ , dat wil zeggen

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

Dus $n\varepsilon_n = -\ln\varepsilon_n\,(1 + o(1)) \to +\infty$ , en opnieuw logaritmen nemen geeft $\ln n + \ln\varepsilon_n = \ln(-\ln\varepsilon_n) + o(1)$ . Omdat $\ln(-\ln \varepsilon_n) = o(\ln(1/\varepsilon_n))$ , volgt $\ln\varepsilon_n \sim -\ln n$ , waaruit $\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) .

Oefening 6.6 ★★

Voer Voorbeeld 6.23 één orde verder door:

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

(Schrijf $\cot y_n = x_n$ exact, ontwikkel $\cot y = \frac1y - \frac y3 + o(y)$ en $x_n = n\pi(1 + \frac{1}{2n} - \dots)$ , en identificeer.)

Oplossing

Oplossing van Oefening 6.6.

Exacte betrekking: $\cot y_n = x_n = n\pi + \frac\pi2 - y_n$ met $y_n \sim \frac{1}{n\pi}$ (Voorbeeld 6.23). Ontwikkel $\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),

(de termen $-y_n$ en $-\frac{y_n}{3}$ zijn $O(\frac1n)$ ). Inverteer:

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).

Bijgevolg is

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).

Oefening 6.7 ★★

Bepaal $\lim_{n\to\infty} \dfrac{1}{n!}\sum_{k=0}^{n} k!$ (begrens de som van alle termen op de laatste twee na), en leid daaruit de asymptotische ontwikkeling $\sum_{k \leq n} k! = n!\bigl(1 + \frac1n + O(n^{-2})\bigr)$ af.

Oplossing

Oplossing van Oefening 6.7.

Splits de twee grootste termen af:

\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)! .

Dus $1 \leq \frac{1}{n!}\sum k! \leq 1 + \frac{2}{n}$ : de limiet is $1$ . Verfijning: $\frac{(n-1)!}{n!} = \frac1n$ , en de ruwe grens $\sum_{k \leq n-2}k! \leq (n-1)!$ laat zich op dezelfde manier aanscherpen: $\sum_{k\leq n-2} k! = (n-2)!\,(1 + O(\frac1n)) = O\bigl(\frac{n!}{n^2}\bigr)$ . Bijgevolg is

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

Oefening 6.8 ★★★

Zij $u_0 > 0$ en $u_{n+1} = u_n + \dfrac{1}{u_n}$ . Bewijs dat $u_n \to \infty$ , vervolgens dat $u_n \sim \sqrt{2n}$ (bestudeer $u_n^2$ : haar toenamen zijn $2 + u_n^{-2}$ ; sommeer), en verfijn:

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

(Uit $u_n^2 = 2n + \sum_{k<n} u_k^{-2} + u_0^2$ en $u_k^2 \sim 2k$ : de som is $\sim \frac12\ln n$ volgens Stelling 6.6.)

Oplossing

Oplossing van Oefening 6.8.

$(u_n)$ stijgt; was zij begrensd, dan zou zij naar een $\ell$ convergeren met $\ell = \ell + \frac1\ell$ : absurd. Dus $u_n \to \infty$ .

Kwadraten: $u_{n+1}^2 = u_n^2 + 2 + u_n^{-2}$ , dus

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

De som is $o(n)$ (de termen gaan naar $0$ ; Cesàro), dus $u_n^2 \sim 2n$ en $u_n \sim \sqrt{2n}$ .

Verfijning: $\frac{1}{u_k^2} \sim \frac{1}{2k}$ , dus levert de vergelijking (Stelling 6.6, of equivalenten van partiële sommen van positieve reeksen) $\sum_{k<n} u_k^{-2} \sim \frac12 \ln n$ . Bijgevolg is

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).

Oefening 6.9 ★★★

(Een riemannsom met een addertje) Bepaal het asymptotische gedrag van

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

(Haal $n$ buiten haakjes: $S_n = \frac1n\sum_k \bigl(1 + \frac{k\ln n}{n}\bigr)^{-1}$ ; herken een som van het type Riemann met een traag variërende parameter $t = \ln n$ , bereken $\int_0^1 \frac{\dd u}{1 + tu} = \frac{\ln(1+t)}{t}$ , en besluit dat $S_n \sim \frac{\ln\ln n}{\ln n}$ .)

Oplossing

Oplossing van Oefening 6.9.

Haal $n$ buiten haakjes en zet $t = \ln n$ :

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

Bij vaste $t$ is de som een riemannsom van $u \mapsto \frac{1}{1 + tu}$ op $\intcc{0}{1}$ ; de functie is monotoon in $u$ , dus wordt de riemannsom ingesloten door de integraal, één maaswijdte verschoven:

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

(de vergelijking van de riemannsommen van een monotone functie met haar integraal, geldig voor elke $n$ met haar eigen $t = \ln n$ ). Nu is $\int_0^1 \frac{\dd u}{1 + tu} = \frac{\ln(1 + t)}{t}$ en $\frac1n = o\bigl(\frac{\ln t}{t}\bigr)$ : bijgevolg

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

Oefening 6.10 ★

Bewijs de identiteit $(\ln n)^{\ln n} = n^{\ln\ln n}$ , en rangschik daarna de volgende grootheden bij oneindig in stijgende $o(\cdot)$ -volgorde, met bewijs: $n^2$ , $(\ln n)^{\ln n}$ , $2^n$ , $n!$ , $n^n$ .

Oplossing

Oplossing van Oefening 6.10.

Identiteit: $(\ln n)^{\ln n} = \eu^{\ln n\,\ln\ln n} = \bigl(\eu^{\ln n}\bigr)^{\ln\ln n} = n^{\ln\ln n}$ . Rangschikking: vergelijk logaritmen. $\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, of de ruwere insluiting $\ln n! \sim n\ln n$ ); $\ln(n^n) = n\ln n$ . Omdat $2\ln n = o(\ln n\ln\ln n)$ , $\ln n\ln\ln n = o(n)$ , $n\ln 2 = o(n\ln n - n)$ , en $n \ln n - n \sim n\ln n$ terwijl $n! / n^n \to 0$ (het verschil van de logaritmen is $-n + O(\ln n) \to -\infty$ ), volgt

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).

(Bij elke stap: het verschil van de logaritmen gaat naar $+\infty$ , dus gaat de verhouding naar $0$ .)

Oefening 6.11 ★★

(Staart van $\sum 1/k^2$ , twee termen) Bewijs met de exacte telescopering $\sum_{k > n} \frac{1}{k(k+1)} = \frac{1}{n+1}$ en de splitsing $\frac1{k^2} = \frac{1}{k(k+1)} + \frac{1}{k^2(k+1)}$ dat

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

Oplossing

Oplossing van Oefening 6.11.

Splits $\frac1{k^2} = \frac1{k(k+1)} + \frac1{k^2(k+1)}$ en sommeer voor $k > n$ :

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

waarbij de eerste som exact telescopeert ( $\frac1{k(k+1)} = \frac1k - \frac1{k+1}$ ). Voor de tweede: $\frac{1}{k^2(k+1)} = \frac1{k^3} + O\bigl(\frac1{k^4}\bigr)$ (want $\frac{1}{k^2(k+1)} - \frac1{k^3} = \frac{-1}{k^3(k+1)}$ ), en de vergelijking met de integraal geeft $\sum_{k>n}\frac1{k^3} = \frac1{2n^2} + O\bigl(\frac1{n^3}\bigr)$ en $\sum_{k>n}\frac1{k^4} = O\bigl(\frac1{n^3}\bigr)$ . Bijgevolg is

\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),

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

Oefening 6.12 ★★★

Zij $u_0 = \frac12$ en $u_{n+1} = u_n + \eu^{-u_n}$ . Bewijs dat $u_n \to \infty$ , en leid vervolgens — door $v_n = \eu^{u_n}$ te zetten en aan te tonen dat $v_{n+1} = v_n + 1 + \frac{1}{2v_n} + O\bigl(v_n^{-2}\bigr)$ — af dat

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

Oplossing

Oplossing van Oefening 6.12.

$(u_n)$ stijgt; was zij begrensd, dan zou zij naar een eindige $\ell$ convergeren met $\ell = \ell + \eu^{-\ell}$ : onmogelijk. Dus $u_n \to \infty$ . Zij $v_n = \eu^{u_n} \to \infty$ ; dan is

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).

Het sommeren van $v_{k+1} - v_k = 1 + O(1)$ geeft eerst $v_n = n + O(n)$ , dus $v_n \geq cn$ vanaf zekere rang; opnieuw sommeren met $\frac1{2v_k} = O(\frac1k)$ geeft $v_n = n + O(\ln n)$ . Nog een ronde: $\frac{1}{2v_k} = \frac{1}{2k}\bigl(1 + O\bigl(\tfrac{\ln k}k\bigr)\bigr)$ , dus

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

Ten slotte $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 Probleem: Bootstrappen, van Euler–Maclaurin tot de priemgetallen

Een impliciete of opgestapelde grootheid geeft haar asymptotiek zelden in één keer prijs; men haalt haar in rondes binnen, waarbij elke ronde de vorige schatting terugvoert in de definiërende betrekking. Deze weekendopgave traint die lus op nieuwe vergelijkingen, bewijst de formule van Euler–Maclaurin van eerste orde (de trapeziumverbetering van de vergelijking van reeks en integraal, met rigoureuze foutbalken), keert $x\ln x = n$ om, en int de beroemdste cheque van de methode: uit de zonder bewijs aangenomen priemgetalstelling volgt de asymptotische wet $p_n \sim n\ln n$ voor het $n$ -de priemgetal.

Probleem 6.1

Weekendopgave — de correctie van Euler–Maclaurin en de asymptotiek van het $n$ -de priemgetal

Deel I — De bootstraplus op een nieuwe vergelijking.

Bewijs de bewering over eenduidigheid uit Definitie 6.2: geldt $f = \sum_{i\leq k} c_i\varphi_i + o(\varphi_k) = \sum_{i \leq k} c_i'\varphi_i + o(\varphi_k)$ langs dezelfde schaal, dan is $c_i = c_i'$ voor alle $i$ . Voer daarna het gemengde voorbeeld uit de cursus één sport verder door:

$\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),$

en leg uit waarom er geen term $\frac{c}{x^2}$ verschijnt.
Toon aan dat de vergelijking $\eu^x + x = n$ voor elke $n \geq 1$ precies één reële oplossing $x_n$ heeft, en dat $x_n \to +\infty$ met $x_n \sim \ln n$ .
Bootstrap tweemaal:

$x_n = \ln n - \frac{\ln n}{n} - \frac{(\ln n)^2}{2n^2} + o\Bigl(\frac{(\ln n)^2}{n^2}\Bigr).$
Controleer numeriek bij $n = 1000$ : vergelijk $x_{1000} \approx 6.90083$ met de waarden van vraag 3 met één, twee en drie termen, tot op vijf decimalen.

Deel II — Euler–Maclaurin, eerste orde.

Bewijs de identiteit met de trapeziumkern: voor $g$ van klasse $C^2$ op $\intcc{0}{1}$ geldt

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

(integreer $\frac12 t(1-t)g''$ tweemaal partieel).
Zij $f$ van klasse $C^2$ op $\intco{1}{+\infty}$ met $\int_1^\infty \abs{f''} < \infty$ . Toon aan dat

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

naar een constante $E$ convergeert, met de staartgrens $\abs{E - E_n} \leq \frac18\int_n^\infty\abs{f''}$ : de formule van Euler–Maclaurin tot op de eerste orde.
Pas dit toe op $f(t) = \frac1t$ : bewijs dat

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

wat Oefening 6.3 versterkt (identificeer de constante met $\gamma$ door met Voorbeeld 6.7 te vergelijken).
Haal de volgende coëfficiënt binnen: toon aan dat $\varepsilon_n = -\frac{1}{12n^2} + o\bigl(\frac1{n^2}\bigr)$ (de toenamen van $E_n$ zijn $\frac12\int_0^1t(1-t)f''(n+t)\dd t = \frac1{12}f''(n) + o(f''(n))$ ; sommeer de staart met Stelling 6.6).
Pas vraag 6 toe op $f = \ln$ : leid in drie regels opnieuw de convergentie af van $d_n = \ln n! - (n + \frac12)\ln n + n$ (stap 1 van Stelling 6.13), met als bonus de foutsnelheid $d_n = d + O\bigl(\frac1n\bigr)$ .
Pas vraag 6 toe op $f(t) = \frac{1}{\sqrt t}$ : toon aan dat

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

voor zekere constante $c$ , en evalueer alle termen bij $n = 10^4$ (de constante is $c \approx -1.4604$ ).

Deel III — Omkeren: de vergelijking $x\ln x = n$ .

Toon aan dat $x\ln x = n$ voor $n \geq 1$ precies één oplossing $x_n \in \intco{1}{+\infty}$ heeft, dat $x_n \to \infty$ , en dat $\ln x_n \sim \ln n$ .
Leid de omkering met één term af, $x_n \sim \dfrac{n}{\ln n}$ , en bootstrap daarna nog eens:

$\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 bij $n = 10^6$ : het werkelijke nulpunt is $x \approx 87\,848$ ; vergelijk met de waarden met één term ( $\approx 72\,382$ ) en met twee termen ( $\approx 86\,140$ ), en verklaar de trage winst (de ontwikkelingsparameter is $\frac{\ln\ln n}{\ln n}$ , bij $n = 10^6$ slechts $\approx 0.19$ ).
We nemen nu de priemgetalstelling zonder bewijs aan: het aantal $\pi(x)$ priemgetallen $\leq x$ voldoet aan $\pi(x) \sim \frac{x}{\ln x}$ als $x \to \infty$ (eerlijk bewezen in het volume van bachelorjaar 3). Schrijf $p_n$ voor het $n$ -de priemgetal, verantwoord dat $\pi(p_n) = n$ , en voer de omkering van de vragen 11–12 uit om te bewijzen dat

$p_n \sim n \ln n .$
Opbrengsten: (a) toon aan dat $\sum_{k \leq n} p_k \sim \frac{n^2\ln n}{2}$ (vergelijk $\sum k\ln k$ met $\int t\ln t\,\dd t$ ); (b) bereken bij benadering de kans dat een uniform gekozen geheel getal van $100$ cijfers priem is ( $\ln 10^{100} \approx 230.26$ : ongeveer één op $230$ ).

Deel IV — De methode geëxporteerd: $x\tan x = 1$ .

Toon aan dat de vergelijking $\tan x = \frac1x$ voor elke $n \geq 1$ precies één oplossing $x_n$ heeft in $\intoo{n\pi}{\,n\pi + \frac\pi2}$ , en dat $z_n = x_n - n\pi \to 0^+$ .
Eén term: $z_n \sim \dfrac{1}{n\pi}$ .
Toon aan dat de ontwikkeling van $z_n$ geen term $\frac{c}{n^2}$ heeft: $z_n = \frac1{n\pi} + O\bigl(\frac{1}{n^3}\bigr)$ .
Drie termen: bewijs met $\arctan u = u - \frac{u^3}3 + O(u^5)$ en $\frac1{x_n} = \frac{1}{n\pi} - \frac{z_n}{(n\pi)^2} + O(n^{-3}\cdot z_n^2)$ dat

$x_n = n\pi + \frac{1}{n\pi} - \frac{4}{3\pi^3 n^3} + o\Bigl(\frac{1}{n^3}\Bigr).$
Controleer bij $n = 3$ : het werkelijke nulpunt is $x_3 \approx 9.5293344$ ; vergelijk de waarden met één en met drie termen, en zet dit in één zin af tegen de $\tan x = x$ uit de cursus (Voorbeeld 6.23): waar elke rij in haar venster ligt, en waarom.

Deel V — Een dynamische bootstrap, de spelregels, en de synthese.

Zij $u_0 \in \intoo{0}{\pi}$ en $u_{n+1} = \sin u_n$ . Toon aan dat $u_n$ dalend naar $0$ gaat, en bereken de limiet van $\dfrac{1}{u_{n+1}^2} - \dfrac{1}{u_n^2}$ (ontwikkel $\sin^{-2}$ via $\sin u = u - \frac{u^3}6 + o(u^3)$ ).
Leid daaruit, via de gemiddelden van Cesàro (volume van bachelorjaar 1), de klassieke uitspraak

$u_n \sim \sqrt{\frac{3}{n}}$

af.
(Gecertificeerde numeriek) Toon met de rigoureuze grens van vraag 7 aan dat het evalueren van $\ln n + \gamma + \frac1{2n}$ bij $n = 10^6$ de waarde $H_{10^6}$ oplevert met een fout van hoogstens $1.25\cdot10^{-13}$ — een som van een miljoen termen, met drie termen tot op dertien cijfers berekend.
(Spelregels) Bewijs of weerleg, met bewijzen of tegenvoorbeelden: (a) geldt $u_n \sim v_n \to +\infty$ , dan $\ln u_n \sim \ln v_n$ ; (b) geldt $u_n \sim v_n$ , dan $\eu^{u_n} \sim \eu^{v_n}$ ; (c) geldt $f \sim g$ bij $+\infty$ (met $f, g$ differentieerbaar), dan $f' \sim g'$ .
(Synthese) In telkens één zin: de bootstraplus van Methode 6.22 zoals gebruikt in de Delen I, III en IV; wat de trapeziumcorrectie toevoegt aan Stelling 6.6; waarom het omkeren van $x\ln x$ juist de brug is van $\pi(x)$ naar $p_n$ ; en welke van de regels uit vraag 24 welke stap beschermde. Noem de twee toppen: de formule van Euler–Maclaurin (eerste orde), en de asymptotische wet voor het $n$ -de priemgetal.

Oplossing

Oplossing van Probleem 6.1.

1. Aftrekken van de twee ontwikkelingen geeft $\sum_i (c_i - c_i')\varphi_i = o(\varphi_k)$ . Verschilt een coëfficiënt, zij $i_0$ de eerste: deling door $\varphi_{i_0}$ en het gebruik van $\varphi_j = o(\varphi_{i_0})$ voor $j > i_0$ geeft $c_{i_0} - c_{i_0}' = o(1)$ , dus nul: tegenspraak. Voor de ontwikkeling: met $u = \frac{\ln x}x \to 0$ is

\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).

Er verschijnt geen term $\frac c{x^2}$ omdat de ontwikkeling een meetkundige reeks in $u = \frac{\ln x}{x}$ is: elke term draagt voorbij de eerste evenveel machten van $\ln x$ als van $\frac1x$ ; de sport $\frac1{x^2}$ van de schaal (de coëfficiënt bij $(\ln x)^0$ ) ontbreekt eenvoudigweg, met coëfficiënt $0$ .

2. $f(x) = \eu^x + x$ is continu en strikt stijgend, met limieten $-\infty$ en $+\infty$ : dus een bijectie $\R \to \R$ , zodat $x_n = f^{-1}(n)$ bestaat en eenduidig is, en $x_n \to +\infty$ ( $f^{-1}$ stijgt naar $+\infty$ ). Uit $\eu^{x_n} = n - x_n$ volgt $x_n = \ln(n - x_n) \leq \ln n$ , dus $x_n/n \to 0$ en $x_n = \ln n + \ln(1 - x_n/n) = \ln n + o(1) \sim \ln n$ .

3. Schrijf $u_n = x_n/n$ . Tweede ronde: $u_n = \frac{\ln n + o(1)}{n}$ , dus

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).

Derde ronde: nu is $u_n = \frac{\ln n}{n} - \frac{\ln n}{n^2} + o\bigl(\frac{\ln n}{n^2}\bigr)$ , en $\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),

waarbij de term $\frac{\ln n}{n^2}$ in $o\bigl(\frac{(\ln n)^2}{n^2}\bigr)$ wordt opgeslokt.

4. Bij $n = 1000$ : $\ln 1000 \approx 6.90776$ (fout $7\cdot10^{-3}$ ); met twee termen $6.90085$ (fout $2\cdot10^{-5}$ ); met drie termen $6.90082$ (fout onder $10^{-5}$ ), tegenover $x_{1000} \approx 6.90083$ . Elke ronde koopt ruwweg de voorspelde factor $\frac{\ln n}{n}$ .

5. Twee partiële integraties, vanaf rechts: met $\frac{\dd}{\dd t}\bigl[\tfrac12t(1-t)\bigr] = \tfrac12 - t$ en $t(1-t)$ dat in beide eindpunten verdwijnt, is

\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 .

Herschikt is dat de gevraagde identiteit.

6. Bereken de toename en pas dan vraag 5 toe op $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*}

Omdat $0 \leq t(1-t) \leq \frac14$ , is $\abs{E_{n+1} - E_n} \leq \frac18\int_n^{n+1}\abs{f''}$ , en de som daarvan over $n$ convergeert wegens de hypothese: $(E_n)$ convergeert (absoluut sommeerbare toenamen) naar zekere $E$ , met

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

7. Voor $f(t) = \frac1t$ is $f''(t) = \frac2{t^3}$ en $\int_1^\infty\abs{f''} = 1 < \infty$ . Vraag 6 geeft

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

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

8. Uit de formule voor de toename in vraag 6:

\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),

met $\frac{1}{(k+t)^3} = \frac1{k^3} + O\bigl(\frac1{k^4}\bigr)$ uniform voor $t \in \intcc01$ . Met $\int_0^1 t(1-t) = \frac16$ en $\sum_{k\geq n}\frac1{k^3} \sim \frac{1}{2n^2}$ (Stelling 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. Voor $f = \ln$ is $f''(t) = -\frac1{t^2}$ , absoluut integreerbaar. Vraag 6 geeft

\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),

dus $d_n = 1 + E + O\bigl(\frac1n\bigr)$ : de convergentie van $(d_n)$ — stap 1 van Stelling 6.13 — plus de snelheid $O(1/n)$ . (De waarde van de limiet volgens Stirling geeft $E = \ln\sqrt{2\pi} - 1$ .)

10. Voor $f(t) = t^{-1/2}$ is $f''(t) = \frac34 t^{-5/2}$ , absoluut integreerbaar. Vraag 6 geeft

\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),

met $c = E - \frac32$ . Bij $n = 10^4$ : $2\sqrt n = 200$ , $c \approx -1.46035$ , $\frac1{2\sqrt n} = 0.005$ : voorspeld $198.54465$ , en inderdaad is $\sum_{k\leq10^4}k^{-1/2} = 198.544645\dots$ — drie termen, zeven cijfers.

11. $t \mapsto t\ln t$ is continu en strikt stijgend op $\intco1\infty$ (afgeleide $\ln t + 1 \geq 1$ ), van $0$ tot $+\infty$ : dus bestaat er een unieke $x_n$ , en $x_n \to \infty$ (anders zou $x_n\ln x_n$ begrensd blijven). Logaritmen nemen in $x_n\ln x_n = n$ geeft $\ln x_n + \ln\ln x_n = \ln n$ ; omdat $\ln\ln x_n = o(\ln x_n)$ , geeft deling door $\ln x_n$ dat $\frac{\ln n}{\ln x_n} \to 1$ : dus $\ln x_n \sim \ln n$ .

12. Uit $x_n = \frac{n}{\ln x_n}$ en $\ln x_n \sim \ln n$ volgt $x_n \sim \frac{n}{\ln n}$ . Volgende ronde: $\ln\ln x_n = \ln\bigl(\ln n\,(1 + o(1))\bigr) = \ln\ln n + o(1)$ , dus $\ln x_n = \ln n - \ln\ln n + o(1)$ en

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. Bij $n = 10^6$ : $\frac{n}{\ln n} \approx 72\,382$ ( $18\%$ ernaast), met twee termen $\approx 86\,140$ ( $1.9\%$ ernaast), tegenover de werkelijke $x \approx 87\,848$ . De winst per ronde is slechts de factor $\frac{\ln\ln n}{\ln n} \approx \frac{2.63}{13.8} \approx 0.19$ : logaritmische schalen convergeren tergend langzaam — een feit van het leven overal waar priemgetallen in het spel zijn.

14. Er zijn precies $n$ priemgetallen $\leq p_n$ (namelijk $p_1, \dots, p_n$ ): dus $\pi(p_n) = n$ . De priemgetalstelling (aangenomen; volume van bachelorjaar 3) geeft $n = \pi(p_n) \sim \frac{p_n}{\ln p_n}$ , dat wil zeggen $p_n \sim n\ln p_n$ : dat is de vergelijking $x\ln x \approx n$ , achterstevoren gelezen. Logaritmen nemen: $\ln p_n = \ln n + \ln\ln p_n + o(1)$ , en $\ln\ln p_n = o(\ln p_n)$ dwingt $\ln p_n \sim \ln n$ af, net als in vraag 11. Terugsubstitueren geeft

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

15. (a) Leg $\varepsilon > 0$ vast; voor grote $k$ is $(1 - \varepsilon)k\ln k \leq p_k \leq (1 + \varepsilon)k\ln k$ . Met de vergelijking met de stijgende $t\ln t$ (insluiting van het type Stelling 6.6) is $\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$ . Bijgevolg is $\sum_{k\leq n}p_k = \frac{n^2\ln n}{2}(1 + O(\varepsilon) + o(1))$ voor elke $\varepsilon$ : dus $\sum_{k\leq n}p_k \sim \frac{n^2\ln n}2$ . (b) Volgens de priemgetalstelling is onder de gehele getallen tot $10^{100}$ een fractie $\sim \frac{1}{\ln 10^{100}} = \frac1{230.26\dots}$ priem: een uniform gekozen geheel getal van $100$ cijfers is priem met kans ongeveer $\frac1{230}$ .

16. Op $\intoo{n\pi}{n\pi + \frac\pi2}$ is $g(x) = \tan x - \frac1x$ continu en strikt stijgend ( $g' = 1 + \tan^2x + \frac1{x^2} > 0$ ), met $g \to -\frac1{n\pi} < 0$ aan de linkerkant en $g \to +\infty$ aan de rechterkant: dus precies één nulpunt $x_n$ . Omdat $\tan z_n = \tan x_n = \frac1{x_n} \to 0$ met $z_n \in \intoo{0}{\frac\pi2}$ , volgt $z_n \to 0^+$ .

17. Er geldt $\tan z_n \sim z_n$ en $\frac1{x_n} \sim \frac1{n\pi}$ : dus $z_n \sim \frac1{n\pi}$ .

18. Er is $z_n = \arctan\frac1{x_n}$ met $\arctan u = u + O(u^3)$ . Met $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),

dus $z_n = \frac1{n\pi} + O\bigl(\frac1{n^3}\bigr)$ : de sport $\frac{c}{n^2}$ heeft coëfficiënt $0$ , omdat de eerste correctie op $\frac1{x_n}$ zelf van de grootte $\frac{z_n}{n^2} = O(n^{-3})$ is.

19. Vul $z_n = \frac1{n\pi} + O(n^{-3})$ in de vorige formule in:

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

en dan $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. Bij $n = 3$ : met één term $9.53088$ , met drie termen $9.52929$ , tegenover het werkelijke nulpunt $9.52933$ : fouten $1.5\cdot10^{-3}$ en $5\cdot10^{-5}$ . Contrast: bij $\tan x = x$ moet het nulpunt $\tan$ enorm maken, dus kruipt het tegen het rechter uiteinde $n\pi + \frac\pi2$ van het venster aan, op afstand $\sim\frac1{n\pi}$ vóór de asymptoot; bij $x\tan x = 1$ moet het nulpunt $\tan$ minuscuul maken, dus ligt het net voorbij het linker uiteinde $n\pi$ , op afstand $\sim\frac1{n\pi}$ na het nulpunt. Dezelfde methode, gespiegelde geografie.

21. Er geldt $\sin u < u$ op $\intoo0\pi$ , en $\sin$ beeldt $\intoo0\pi$ af in $\intoc01 \subseteq \intoo0\pi$ : na één stap ligt $u_1 \in \intoc{0}{1}$ , en daarna daalt $(u_n)$ en is zij van onderen door $0$ begrensd: zij convergeert dus naar een vast punt van $\sin$ , dat wil zeggen naar $0$ . Ontwikkeling: $\sin u = u(1 - \frac{u^2}6 + o(u^2))$ , dus

\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. Volgens Cesàro (volume van bachelorjaar 1) convergeert het gemiddelde van de toenamen naar dezelfde limiet:

\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 ,

dus $u_n^2 \sim \frac3n$ en, omdat alle termen positief zijn, $u_n \sim \sqrt{3/n}$ .

23. Volgens vraag 7 is $\abs{H_n - \ln n - \gamma - \frac1{2n}} \leq \frac1{8n^2}$ . Bij $n = 10^6$ is die grens $\frac{1}{8\cdot10^{12}} = 1.25\cdot10^{-13}$ : drie berekende termen leveren de harmonische som van een miljoen termen tot op dertien cijfers, met een volledig rigoureus foutcertificaat — en daar draait een asymptotische formule met expliciete restterm precies om.

24. (a) Waar: $\ln u_n - \ln v_n = \ln\frac{u_n}{v_n} \to 0$ terwijl $\ln v_n \to +\infty$ , dus gaat de verhouding van de logaritmen naar $1$ . (b) Onwaar: $u_n = n + 1 \sim v_n = n$ , maar $\eu^{u_n}/\eu^{v_n} = \eu \neq 1$ . Equivalentie verdraagt additieve fouten $o(1)$ in de exponent, geen $O(1)$ . (c) Onwaar: $f(x) = x + \sin(x^2) \sim g(x) = x$ bij $+\infty$ , maar $f'(x) = 1 + 2x\cos(x^2)$ oscilleert onbegrensd terwijl $g' = 1$ : de afgeleiden van equivalente functies hoeven in het geheel niet vergelijkbaar te zijn.

25. De lus van Methode 6.22 liep drie keer identiek: lokaliseer het nulpunt, haal een ruwe term eruit, voer die terug voor de volgende orde — op $\eu^x + x = n$ (Deel I), op $x\ln x = n$ (Deel III) en op $x\tan x = 1$ (Deel IV). De trapeziumcorrectie tilt de vergelijking van reeks en integraal op van “het verschil convergeert” naar een expliciete term $\frac{f(1) + f(n)}2$ met een gecertificeerde restterm $O(\int_n^\infty \abs{f''})$ — constanten en foutbalken in plaats van louter convergentie. De brug naar de priemgetallen is zuivere omkering: de priemgetalstelling zegt $\pi(x)\ln x \approx x$ , dus lost $p_n$ , gedefinieerd door $\pi(p_n) = n$ , een vergelijking $x\ln x = n$ op — en erft haar asymptotiek. Regel (a) van vraag 24 legitimeerde elke overgang van $u_n \sim v_n$ naar $\ln u_n \sim \ln v_n$ (vragen 11 en 14); dat (b) onwaar is, is de reden dat we equivalenties nooit exponentiëren. De toppen: de formule van Euler–Maclaurin tot op de eerste orde (vraag 6), en de asymptotische wet $p_n \sim n\ln n$ voor het $n$ -de priemgetal (vraag 14).

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst