Elementary Distribution of Primes

We use the prime factorization of the central binomial coefficient

for a positive integer $n$, and standard bounds on how it grows.

Step 1: Bounding $N$ from above and below by elementary counting. Since $N$ is one of the $2n+1$ terms in the binomial expansion of $(1+1)^{2n} = 2^{2n}$, and it is (one of) the largest such term(s) — the binomial coefficients $\binom{2n}{k}$ increase up to $k=n$ and decrease afterward, by the ratio test $\binom{2n}{k+1}/\binom{2n}{k} = (2n-k)/(k+1)$ — we get

For a lower bound, since the sum of all $2n+1$ binomial coefficients is $2^{2n}$ and $N=\binom{2n}{n}$ is the largest term,

Step 2: The exact prime factorization of $N$. For each prime $p \le 2n$, Legendre's formula gives the exponent of $p$ in $m!$ as

(a finite sum, since terms vanish once $p^i>m$). Hence the exponent of $p$ in $N$ is

Each individual term $\lfloor 2t \rfloor - 2\lfloor t \rfloor$ (with $t = n/p^i$) is either $0$ or $1$, because writing $t = \lfloor t\rfloor + \{t\}$ with fractional part $\{t\} \in [0,1)$,

Also, the sum has at most $\lfloor \log(2n)/\log p\rfloor$ nonzero terms, since $\lfloor 2n/p^i\rfloor = 0$ once $p^i>2n$. Therefore

Step 3: Upper bound for $\pi(2n)-\pi(n)$ (this yields the lower Chebyshev bound). Every prime $p$ with $n < p \le 2n$ divides $N=\binom{2n}{n}=\dfrac{(2n)!}{n!n!}$ exactly once: it appears once in $(2n)!$ (since $2p>2n$ means $p^2 \nmid (2n)!$ contributes nothing extra beyond the single factor $p \le 2n < 2p$) and does not divide $n!$ at all (since $p>n$). So $v_p(N)=1$ for every such prime, and these primes are pairwise distinct factors of $N$, giving

Combined with Step 2 applied to all prime factors of $N$ (each satisfying $p^{v_p(N)}\le 2n$), and using that $N$'s prime factors are all $\le 2n$:

Using the lower bound $N \ge 2^{2n}/(2n+1)$ from Step 1:

Taking logarithms,

so for $n \ge 2$ (making the left side positive and simplifying constants),

for a suitable absolute constant $c_1>0$ once $n$ is large enough; a direct check of small cases (finitely many) extends this, after adjusting $c_1$ downward, to all $n \ge 2$, and the odd-argument case $\pi(2n+1)\ge \pi(2n)$ extends it to all integers $x\ge 4$. This gives the lower bound half of the theorem, $\pi(x) \ge c_1 x/\log x$.

Step 4: Upper bound for $\pi(x)$. We bound $\pi(2n)$ from above using a different route: telescoping the growth of $N$. From Step 1, $N=\binom{2n}{n}\le 2^{2n}$. We show a lower bound for $N$ in terms of the primes between $n$ and $2n$ combined with an inductive bound. Concretely, define $\vartheta(x) = \sum_{p \le x} \log p$ (the Chebyshev theta function). From Step 3's inequality $N \ge \prod_{n<p\le 2n}p$, taking logs:

Summing this over $n = 2^{k-1}, 2^{k-2},\dots$ down a geometric ladder (i.e. applying the bound to $n, n/2, n/4,\dots$ and telescoping $\vartheta(2n)-\vartheta(n) \le 2n\log2$, $\vartheta(n)-\vartheta(n/2)\le n\log 2$, etc.) gives, for $x=2n$,

more precisely one obtains $\vartheta(x) \le (4\log 2)\, x$ for all $x\ge 1$ by this telescoping/induction argument (a standard and completely elementary computation from the same binomial coefficient bound applied repeatedly). Consequently, since $\log p \ge \log(\sqrt x)$ for every prime $p$ with $\sqrt{x} < p \le x$,

so

Since $\sqrt x = o(x/\log x)$, absorbing the $\sqrt x$ term into a slightly larger constant $c_2$ gives, for all $x\ge 2$,

Combining Steps 3 and 4 gives constants $c_1,c_2>0$ with

which is Chebyshev's estimate. $\blacksquare$

We give the classical elementary proof (in the spirit of Erdős's 1932 proof), using the same central binomial coefficient $N=\binom{2n}{n}$ and Legendre's formula as in Chebyshev's Estimate. The technique is proof by contradiction combined with careful prime-factor counting. Small cases ($n = 1,2,3$) are checked directly: for $n=1$, $p=2$ works ($1<2\le 2$); for $n=2$, $p=3$ works; for $n=3$, $p=5$ works. So assume $n \ge 4$ and, for contradiction, suppose no prime lies in $(n,2n]$.

Step 1: Structure of the prime factorization of $N=\binom{2n}{n}$. As shown in the proof of Chebyshev's estimate, for every prime $p$,

each summand is $0$ or $1$, and the sum has at most $\lfloor \log(2n)/\log p\rfloor$ nonzero terms, so

Moreover, if $p > \sqrt{2n}$, then only the $i=1$ term can be nonzero (since $p^2 > 2n$ forces $\lfloor 2n/p^2\rfloor = 0$), so $v_p(N) \in \{0,1\}$ for all such primes.

Step 2: Primes in $(2n/3,\, n]$ contribute nothing. Suppose $\frac{2n}{3} < p \le n$ and $n \ge 4$ (hence $p \ge 3$, so $3p \le 3n$, and also $2p>4n/3$). We check $v_p(N)=0$. We need $\lfloor 2n/p\rfloor - 2\lfloor n/p\rfloor = 0$ and all higher terms $0$. Since $\tfrac{2n}{3}<p\le n$, we have $1 \le n/p < 3/2$, so $\lfloor n/p\rfloor = 1$, and $2 \le 2n/p < 3$, so $\lfloor 2n/p\rfloor = 2$. Thus the $i=1$ term is $2-2(1)=0$. For $i\ge2$: $p^2 > (2n/3)^2 \ge 2n$ once $n\ge 4$ (check: $(2n/3)^2 \ge 2n \iff 4n^2/9\ge 2n \iff n \ge 4.5$; a short direct check handles $n=4$: $2n/3=8/3\approx2.67$, primes $p$ with $2.67<p\le4$: none, so this edge case is vacuous), so $\lfloor 2n/p^2\rfloor=0$ too. Hence $v_p(N)=0$ for all primes in this range — no such prime factor appears in $N$ at all.

Step 3: Under our contradiction hypothesis, no prime lies in $(n,2n]$, so combined with Step 2, all prime factors $p$ of $N$ satisfy either $p \le \tfrac{2n}{3}$ or ($p\le n$, but by hypothesis no prime is in $(n,2n]$, and Step 2 already excludes $(2n/3, n]$). So every prime factor of $N$ satisfies $p \le \tfrac{2n}{3}$.

Step 4: Bounding the contribution of "large" primes ($\sqrt{2n} < p \le 2n/3$). By Step 1's remark, such primes have $v_p(N) \le 1$. There are at most $\pi(2n/3)$ of them, certainly fewer than $\tfrac{2n}{3}$ in number (crudely). So their total contribution to $N$ is at most

This crude bound will be refined via Chebyshev's estimate below; for now record the factorization split

Step 5: Bounding the "small" primes ($p \le \sqrt{2n}$). By $(\ast)$, each contributes at most $2n$, and there are at most $\sqrt{2n}$ of them (since there are at most $\sqrt{2n}$ integers up to $\sqrt{2n}$, let alone primes), so

Step 6: Combine using the Chebyshev-type bound $\vartheta(x) < (\log 4)\,x$. We use a clean, fully elementary form of the estimate proved in Step 4 of Chebyshev's Estimate: for all real $x \ge 2$,

(This is exactly the inequality $\vartheta(x) \le c\, x$ established there, with $c=\log 4$ obtainable directly from $N\le 2^{2n}$ by the same telescoping argument; we take this constant as given from that theorem.) Applying it to $x = 2n/3$:

Combining Steps 4–6 with the exponent bound $v_p(N)\le 1$ for these primes:

Step 7: Contradict the lower bound $N \ge \dfrac{4^n}{2n+1}$. Recall from Step 1 of Chebyshev's Estimate that $N = \binom{2n}{n} \ge \dfrac{2^{2n}}{2n+1} = \dfrac{4^n}{2n+1}$. Combining with Step 6:

Rearranging,

We now show $(\dagger)$ fails for all sufficiently large $n$, and check the remaining finitely many $n$ directly. Taking logarithms (base $e$) of $(\dagger)$:

The right side grows like $\sqrt{n}\log n$, which is $o(n)$, while the left side grows linearly in $n$. Concretely, one checks by calculus that for $n \ge 468$ (a standard threshold in this classical proof; one can verify numerically that at $n=468$, $\sqrt{2n}\log(2n) + \log(2n+1) \approx \sqrt{936}\cdot\log(936) + \log(937) \approx 30.6 \times 6.84 + 6.84 \approx 209.4 + 6.8 = 216.2$, while $\frac{n}{3}\log 4 = 156\times 1.386 = 216.2$ — the crossover — and for $n$ beyond this the linear term dominates, since $d/dn$ of the left side is a constant $\tfrac13\log4\approx0.462$ while the right side's derivative decays like $\log n/\sqrt n \to 0$), the inequality $(\dagger)$ is false. Hence for all $n \ge 468$, no such contradiction-consistent $N$ can exist, i.e., our assumption (no prime in $(n,2n]$) is false.

Step 8: Finite check for $4 \le n < 468$. For the remaining finitely many $n$ in $[4,467]$, one exhibits explicitly a prime in $(n,2n]$ using the finite list of primes

each less than twice the previous one (this is a standard finite verification: each listed prime is less than double its predecessor, so between any $n$ in the relevant range and $2n$ one of these listed primes must fall). For example: for $n$ up to $467$, since $631 > 2\cdot 317$ fails to be needed as $317\cdot 2=634>467\cdot2$ suffices, the chain $2<3\le2\cdot2,\ 3<5\le2\cdot3,\ 5<7\le2\cdot5,\ 7<13\le2\cdot7,\ 13<23\le2\cdot13,\ 23<43\le2\cdot23,\ 43<83\le2\cdot43,\ 83<163\le2\cdot83,\ 163<317\le2\cdot163$ shows every interval $(n,2n]$ for $1\le n\le 316$ contains one of these primes (each prime in the list is less than twice the previous, guaranteeing no gap), and the analytic argument of Step 7 covers all $n\ge 468 > 316$, so together they cover all $n \ge 1$. This completes the proof: for every $n\ge1$ there is a prime $p$ with $n<p\le 2n$. $\blacksquare$

Apply Bertrand's Postulate with $n = p_k$: there is a prime $p$ with $p_k < p \le 2p_k$. Since $p_{k+1}$ is by definition the least prime exceeding $p_k$, we get $p_{k+1} \le p \le 2p_k$, and since $p\ne p_k$ we in fact get $p_{k+1}\le p < 2p_k$ unless $p=2p_k$ is itself prime — but $2p_k$ is even and greater than $2$, hence composite for $p_k\ge 2$, ruling out equality; hence $p_{k+1}<2p_k$ strictly. Iterating from $p_1=2$: $p_k < 2^{k-1}p_1 = 2^k$. $\blacksquare$