Theorem 1 (Euler)

Bertrand’s postulate

Theorem 4. Let n ∈ N. Then there is some prime p such that n < p ≤ 2n.
The first proof is due to Chebyschev, the proof presented here is due to S.S.Pillai.

2n+1

n
Instead of the estimate ²2n < N < 2²ⁿ for N = ²ⁿ employed in the proof of Chebyschev’s theorem we

will use instead the sharper estimate


₂2n


₂2n

in order to show that
₂^√_n < N < ^√_2n (n ≥ 2), (19)

ϑ(n) < 2n log 2(n ≥ 1). (20)
We will first prove the inequalities in (19). Define
_{P =} 1 · 3 · 5 · . . . · (2n − 1) ₌ 1 · 3 · 5 · . . . · (2n − 1) _· 2 · 4 · 6 · . . . · (2n) ₌ (2n)! _,

and so N = 2²ⁿP Now

2 · 4 · 6 · . . . · (2n) 2 · 4 · 6 · . . . · (2n) 2 · 4 · 6 · . . . · (2n)
2²ⁿ(n!)²

₂2

₄2

(2n)²
1 > 1 − ¹ 1 − ¹ . . . 1 − ¹

₂2

₄2

₆2

(2n)²
_{=⇒ 1 >} 1 · 3 3 · 5 5 · 7 (2n − 1)(2n + 1)



⇒
= 1 > (2n + 1)P ² > 2nP ² = ²ⁿ N ².
₂4n
From this we directly obtain the second inequality in (19). For the first one we have
1 > 1 − ¹ 1 − ¹ . . . 1 − ¹

₃2 ₅2
(2n − 1)²

_{=⇒ 1 >} 2 · 4 4 · 6 (2n − 2)2n

₃2 ₅2

1
(2n − 1)²

₂4n

=⇒ 1 > _{4nP 2} = _{4nN 2} .
This then gives us the first inequality, and (19) is proved.
We then prove (20). This trivially holds for n = 1, 2. Now we assume that it holds for some n ≥ 2, we shall show that ϑ(2n − 1) < 2(2n − 1) log 2, which would imply ϑ(2n) = ϑ(2n − 1) < 4n log 2.
Consider the integer

N ₌ 1 2n ₌ (2n)! n
₌ (2n − 1)!
₌ 2n − 1 _.

2 2 n
(n!)² 2n
n!(n − 1)!
n − 1

This is divisible by every prime p with n < p ≤ 2n − 1, and so also by their product, which gives:

Y
N
² ≥ n
≤2n−1


N
p =⇒ log ₂
≥ ϑ(2n − 1) − ϑ(n).

(19) gives us on the other hand

1
log N < 2n log 2 − ₂ log 2n.

Hence, by combining the two, we have

1
ϑ(2n − 1) − ϑ(n) < (2n − 1) log 2 − ₂ log 2n.

By our assumption ϑ(n) < 2n log 2 and so

This implies when n ≥ 2

1
ϑ(2n − 1) < 2n log 2 + (2n − 1) log 2 − ₂ log 2n.


ϑ(2n − 1) < 2(2n − 1) log 2,

which is exactly the sought inequality. Hence, if (20) holds for n, it holds for 2n − 1 and by the previous remark also for 2n. This means that, if it holds for every n ∈ (2^r−1, 2^r], r ≥ 1, then it holds for every n ∈ (2^r, 2^r+1], and so the claim follows by the induction since it holds for 1 and 2.

Now using these results we shall prove the theorem in two parts, one part for the case n ≥ 2⁶ and one for

_{N =} 2n ₌ (2n)! ₌ ^Y _pvp
n < 2⁶. Starting with the first,recall from a previous proof that we have

with

n (n!)²


p≤2n

v = _Σ , _2n , − 2, _n , .
^p _pr _pr
r≥1

Σ
Then
log N = v_p log p.
p≤2n
We partition this sum into the following value ranges for p, calling them ^Σ₁, ^Σ₂, ^Σ₃ ^Σ₄ respectively:

1. 
   n < p ≤ 2n
   
2. 
   
   3
   ²ⁿ < p ≤ n
   
3. 
   
   3
   ^√2n < p ≤ ²ⁿ with n ≥ 5
   

4. p ≤ ^√2n.

p

p

p

p

_p2

p
For ^Σ₁ we have ⁿ < 1, so ⌊ ⁿ ⌋ = 0 and 1 ≤ ²ⁿ < 2 so that ⌊ ²ⁿ ⌋ = 1 and ⌊ ²ⁿ ⌋ = 0. Then v = 1 and we get




1

n
≤2n

n
≤2n

p

p
^Σ = ^Σ v_p log p = ^Σ log p = ϑ(2n) − ϑ(n).

_p

2

p

For ^Σ₂ we have that 1 ≤ ⁿ ≤ ³ , so ⌊ ⁿ ⌋ = 1 and ⌊ ²ⁿ ⌋ = 2; for n ≥ 3 we get ⌊ ²ⁿ ⌋ = 0, giving us in total

^Σ₂ = 0 for n ≥ 3.

_p2
For ^Σ₃ we have n ≥ 5 and ⁿ



p

_p2

_p2
< ²ⁿ < 1, so v
= ⌊ ²ⁿ ⌋ − 2⌊ ⁿ ⌋ = 0 or 1. Therefore

Σ _≤ Σ
log p = ϑ ²ⁿ − ϑ(^√2n).

Now
^{3 √}2n
≤2n/3 ³

p
ϑ(^√2n) = ^Σ log p ≥ log 2 ^Σ 1 = π(^√2n) log 2,

and so
p≤^√2n
p≤^√2n

3
^Σ ≤ ϑ ²ⁿ − π(^√2n) log 2.
3

Finally for ^Σ₄ we use (13) and obtain
v_p ≤ M_p
= log 2n _,

, ,
log p

so that
Σ _≤ Σ _M
log p ≤ ^{Σ log 2n} · log p = log 2n ^Σ 1.

Hence
p

4. 
   p≤2n
   

p≤^√2n
log p
p≤^√2n

Σ
≤ π(^√2n) log 2n.
4
We add up all the sums together and get, for n ≥ 5,

3
log N ≤ ϑ(2n) − ϑ(n) + ϑ ²ⁿ − π(^√2n)(log 2 − log 2n). (21)
We will use this to show that ϑ(2n) − ϑ(n) > 0 for large enough n. For this purpose we use the following three inequalities:

1. 
   log N > 2n log 2 − log(2^√n) which follows from first inequality of (19);
   
2. 
   
   3
   
   3
   
   3
   ϑ ²ⁿ = ϑ , ²ⁿ , < 2, ²ⁿ , log 2 for n ≥ 2 which follows from (20);
   

3. 
   
   2
   π(n) ≤ ⁿ for n ≥ 8, since all even numbers greater than 2 are composite. Combining these three inequalities with (21) we obtain, for n ≥ 32,
   

2

3
ϑ(2n) − ϑ(n) > 2n log 2 − log(2^√n) − ⁴ⁿ log 2 − √²ⁿ log n

2

3
=⇒ ϑ(2n) − ϑ(n) > ²ⁿ − 1 log 2 − √^{2n + 1} ! log n.
It remains to show that this is strictly positive.
This can be manually checked and verified for n = 2⁶, now we check it for n > 2⁶. For this purpose we will rewrite the inequality as

^√ 3 log n 3^√2 log ^√4n

^{2n −} 2 log 2 ⁻ log 2
Treating this as two real functions of the form
^√_4n > 0.

^√ 3 log x 3^√2 log ^√4x
^{2x −} 2 log 2 ^{and −} log 2 ^√_4x ^,
notice that both functions have positive derivatives for x ≥ 2⁶ and their sum is positive for x = 2⁶, hence the sum is positive for all x > 2⁶ and so in particular for every natural number in that range.
Then it follows that ϑ(2n) − ϑ(n) > 0 for n ≥ 2⁶ ,and so Bertrand’s postulate follows for n ≥ 64.
Now for the smaller naturals, consider the primes 2, 3, 5, 7, 13, 23, 43, 67. Each one of these is smaller than twice the previous one, in particular for any n < 64 we may pick one of these primes, which will satisfy Bertrand’s postulate.
Thus we have proven that the postulate holds for every natural number n.

n/ log n
4 Asymptotic bounds for ^π(n) In this section we will prove the following theorem: