En anvendelse i tallteori

La $p_n$ være primtall nummer $n$. Det vil si at $p_1=2,p_2=3,p_3=5$ og så videre. La oss nå ta produktet av alle disse og legge til $1$:

$p_1\cdot \cdot \cdot p_n+1.$

Vi merker at ingen av primtallene $p_1,p_2,...,p_n$ kan dele dette tallet: vi kommer alltid til å få $1$ i rest. Dermed vet vi at det neste primtallet, $p_{n+1}$, ikke kan være større enn dette produktet. Med andre ord har vi

$p_{n+1}\le p_1\cdot \cdot \cdot p_n+1.$

Nå viser vi at $p_n<{2^2}^n$ ved induksjon. Tilfellet $n=1$ er umiddelbart: $2<4$. Anta at $p_k<{2^2}^k$. Vi vet at

$p_{k+1}<{2^2}^1\cdot {2^2}^2\cdot \cdot \cdot {2^2}^k+1=2^{\sum _{i=1}^k{2}^i}+1$

Rekken i eksponenten er geometrisk med kvotient $2$. Vi vet at denne rekker konvergerer til

$\frac{2\left(2^{n-1}-1\right)}{2-1}=2^n-2$

Dermed har vi

$p_{k+1}<2^{2^k-2}+1<2^{2^k+1}$

Dette fullfører induksjonsbeviset, så vi har $p_n<2^{2^n}$ for alle $n$. Dermed må det være minst $n$ primtall under $2^{2^n}$:

$\pi \left({2^2}^n\right)\ge n$

Nå gjør vi antagelsen at $x>e$, og velger et heltall $n$ slik at

$e^{e^{n-1}}<x\le e^{e^n}$

(Merk at dette alltid finnes et slikt heltall, om du er i tvil, se på grafen til funksjonen $f\left(x\right)=e^x$) Når $n=4$, så er $e^{n-1}>2$. Siden eksponentialfunksjonen $e^x$ vokser fortere enn $2x$ (siden $e>2$), så vet vi at $e^{n-1}>2^n$ for alle $n\ge 4$. Dermed har vi, for vårt valg av $n$ og $x$,

$\pi \left(x\right)\ge \pi \left(e^{e^{n-1}}\right)$.

Siden $e^{n-1}>2^n$ for $n\ge 4$ har vi

$\pi \left(e^{e^{n-1}}\right)\ge \pi \left(e^{2n}\right)\ge \pi \left(2^{2n}\right)$.

Men vi har allerede vist at

$\pi \left(2^{2^n}\right)\ge n$.

Men siden $x\le e^{e^n}$, så er $\ln x\le e^n$, og $\ln \left(\ln x\right)\le n$. Dermed har vi

$n\ge \ln \left(\ln x\right)$

og vi har vist at

$\pi \left(x\right)\ge \ln \left(\ln x\right)$.

Merk at beviset ikke holder for veldig små verdier av $x$, men disse kan sjekkes manuelt.