Bertrand's postulate
Despite it's name, Bertrand's postulate is actually a theorem rather than a postulate:
Theorem (Bertrand's Postulate): For every integer [math]\displaystyle{ n \geq 2 }[/math], there is a prime [math]\displaystyle{ p }[/math] satisfying [math]\displaystyle{ n \lt p \lt 2n }[/math].
The relevance of the postulate for the finding primes problem is that it guarantees the existence of a [math]\displaystyle{ k }[/math]-digit prime for any [math]\displaystyle{ k }[/math]. Brute force search thus yields a [math]\displaystyle{ k }[/math]-digit prime after about [math]\displaystyle{ O(10^k) }[/math] steps; this can be considered the "trivial bound" for the problem.
This result was apparently first proved by Chebyshev. For large [math]\displaystyle{ n }[/math], the claim follows as a consequence of the prime number theorem. We will give an elementary proof due to Erdos.
Our proof of Bertrand's postulate starts with a result independent interest, due to Chebyshev.
Lemma (Chebyshev bound): For integers [math]\displaystyle{ n \geq 2 }[/math],
[math]\displaystyle{ \prod_{p \leq n} p \leq 4^n, }[/math]
where the product is over all primes [math]\displaystyle{ p }[/math] less than or equal to [math]\displaystyle{ n }[/math].
The Chebyshev bound tells us that primes can't occur too frequently (for example, with constant density) in the positive integers, for if they did, the product of primes on the left would rise much faster than [math]\displaystyle{ 4^n }[/math]. Although it's not needed for a proof of Bertrand's postulate, there is insight to be gained in expressing this idea in a simple quantitative way. Observe that if [math]\displaystyle{ \pi(n) }[/math] is the number of primes less than or equal to [math]\displaystyle{ n }[/math], then [math]\displaystyle{ \pi(n)! \leq \prod_{p \leq n} p }[/math], simply because the [math]\displaystyle{ k }[/math]th prime must be at least [math]\displaystyle{ k }[/math]. Combining this observation with Chebyshev's bound gives [math]\displaystyle{ \pi(n)! \leq 4^n }[/math]. Taking logarithms of both sides, and applying Stirling's approximation, we see that up to constant factors and small corrections, we have [math]\displaystyle{ \pi(n) \ln \pi(n) \leq n. }[/math] This, in turn, implies that up to constant factors and small corrections, [math]\displaystyle{ \pi(n) \leq n \ln \ln n / \ln n }[/math]. Roughly speaking, the prime numbers are at most logarithmically dense in the positive integers. In fact, the prime number theorem tells us that [math]\displaystyle{ \pi(n) \approx n / \ln n }[/math], as [math]\displaystyle{ n }[/math] becomes large.
Proof: We will prove Chebyshev's bound by inducting on [math]\displaystyle{ n }[/math]. The case when [math]\displaystyle{ n=2 }[/math] is obviously true. Furthermore, if we assume the result when [math]\displaystyle{ n }[/math] is odd, it follows immediately for [math]\displaystyle{ n+1 }[/math], since the left-hand side is not affected by incrementing [math]\displaystyle{ n }[/math]. So we can suppose [math]\displaystyle{ n = 2m }[/math] is even and try to prove the result for [math]\displaystyle{ 2m+1 }[/math]. What we'll aim to show is that:
[math]\displaystyle{ (*) \prod_{m+1 \lt p \leq 2m+1} p \leq 4^m }[/math]
If we can prove this, then multiplying by the inequality [math]\displaystyle{ \prod_{p \leq m+1} p \leq 4^{m+1} }[/math] (which is true by the inductive hypothesis) will give us the desired result. To prove (*), note that every prime [math]\displaystyle{ p }[/math] satisfying [math]\displaystyle{ m+1 \lt p \leq 2m+1 }[/math] must divide [math]\displaystyle{ {2m+1 \choose m} }[/math], since [math]\displaystyle{ p }[/math] appears in the numerator, but not the denominator. Furthermore, the uniqueness of prime factorization means that the product of all such primes must also divide [math]\displaystyle{ {2m+1 \choose m} }[/math], and so we have
[math]\displaystyle{ \prod_{m+1 \lt p \leq 2m+1} p \leq {2m+1 \choose m}. }[/math]
The proof is completed by noting that [math]\displaystyle{ {2m+1 \choose m} }[/math] appears twice in the binomial expansion of [math]\displaystyle{ (1+1)^{2m+1} }[/math], and thus [math]\displaystyle{ {2m+1 \choose m} \leq 4^m }[/math]. QED
There are two main ideas in this proof, and it's worth dwelling on them briefly; it's perhaps also instructive to spend some time thinking about variants of these ideas, and how that might impact the proof. The first idea is that there should be a relationship between products of primes and factorials, e.g.,
[math]\displaystyle{ \prod_{m+1 \lt p \leq 2m+1} p \leq {2m+1 \choose m}. }[/math]
The second idea is that there should be a relationship between combinatorial coefficients like [math]\displaystyle{ {2m+1 \choose m} }[/math] and exponentials with fixed bases, e.g., [math]\displaystyle{ {2m+1 \choose m} \leq 4^m }[/math]. Once these two ideas are firmly in mind, the proof is obvious.
In the light of these comments, it's perhaps not surprising that the idea underlying the proof of Bertrand's postulate is to show that the binomial coefficient [math]\displaystyle{ {2n \choose n} }[/math] must have a prime factor [math]\displaystyle{ p }[/math] such that [math]\displaystyle{ n \lt p \lt 2n }[/math]. Before we get to that, we'll prove a useful fact about the prime factorization of [math]\displaystyle{ {2n \choose n} }[/math]. In particular, our second lemma tells us that [math]\displaystyle{ {2n \choose n} }[/math] has a rather special prime factorization which only involves low powers.
Lemma: Let [math]\displaystyle{ p }[/math] be a prime, and define [math]\displaystyle{ r(p,n) }[/math] to be the largest number such that [math]\displaystyle{ p^{r(p,n)} }[/math] divides [math]\displaystyle{ {2n \choose n} }[/math]. Then [math]\displaystyle{ p^{r(p,n)} \leq 2n }[/math].
This is the essential insight underlying Bertrand's postulate: because we can guarantee that the powers are low, [math]\displaystyle{ {2n \choose n} }[/math] must have many prime factors, and a careful accounting will show that we simply don't have enough if one of them isn't in the range [math]\displaystyle{ n \lt p \lt 2n }[/math].
Proof: To prove this, observe that the prime power of [math]\displaystyle{ p }[/math] in the factorization of [math]\displaystyle{ n! }[/math] is given by [math]\displaystyle{ \sum_{j=1}^{\infty} \lfloor n / p^j \rfloor }[/math]. As a result, [math]\displaystyle{ r(p,n) = \sum_{j=1}^\infty ( \lfloor 2n / p^j \rfloor - 2 \lfloor n / p^j \rfloor) }[/math]. All terms in this sum are either [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ 1 }[/math], and they are always [math]\displaystyle{ 0 }[/math] when [math]\displaystyle{ j \geq \log_p (2n) }[/math], whence [math]\displaystyle{ r(p,n) \leq \log_p (2n) }[/math], which gives the result. QED
As a corollary of the proof of the lemma, we see that when the prime [math]\displaystyle{ p }[/math] is sufficiently large, [math]\displaystyle{ p \geq \sqrt{n} }[/math], then only a single term in the sum for [math]\displaystyle{ r(p,n) }[/math] survives, [math]\displaystyle{ r(p,n) = \lfloor 2n / p \rfloor - 2 \lfloor n / p \rfloor }[/math]. This corollary perhaps appears somewhat unmotivated now, but will be useful in a moment.
We now have all the elements in place to make a proof of Bertrand's postulate straightforward.
Proof of Bertrand's postulate: To be added: the proof is not difficult, given the ideas above, but is a bit detailed and tedious.
