Bertrand's Postulate - 2025-03-30

Bertrand's Postulate

Hello, I'm going to walk you through a proof. One of my favorites. I discovered this for one of my college projects, it's called Bertrand's Postulate and it states that:

For any integer $n > 1$, there's always at least one prime number $ p $ such that $ n < p < 2n$.

The Beginning

To start, I want to convince you that $\binom{2n}{n} \geq \frac{4^n}{2n+1}$ for a particular reason. Let's quickly get that out of the way.

From the Binomial Theorem we have: $$(x+y)^n = \sum^{n}_{i=0}\binom{n}{i} x^{n-i}y^i$$ Now, we want to consider the case when $n$ is replaced by $2n$ because we want to observe the relationship between $\binom{2n}{n}$ and $4^n$. It would also be nice if the $x$ and $y$ went away so let's let $x = 1,\ y = 1$. We get $$(2)^{2n} = \sum^{2n}_{i=0}\binom{2n}{i}$$ Which is the same as $$4^n = \sum^{2n}_{i=0}\binom{2n}{i}$$ Now consider the fact that $\binom{2n}{n}$ is the greatest term in this sequence (proof by just look at pascals triangle or just think about choosing things lol). You can conclude safely that the maximum term in a sum must be greater than or equal to it's average. Since this is a $2n + 1$ term sum, $$\binom{2n}{n} \geq \frac{4^n}{2n+1}$$ yay.

The Goal

I made you understand this inequality because it is the heart of this proof. The goal now is to assume our postulate is false, show that there is an upper bound on $\binom{2n}{n}$, and show that for $n \geq 468$ this bound falls below $\frac{4^n}{2n+1}$ thus contradicting the inequality we just proved... $\binom{2n}{n} \geq \frac{4^n}{2n+1}$. Therefore proving our postulate to be true :)

Onwards

In order to show this contradiction there's a few facts we will have to come about. They are:

If $n \geq 3$, there is no prime $p$ such that $\frac{2}{3}n \lt p \leq n$ and $p \mid \binom{2n}{n}$.
If $p \mid \binom{2n}{n} $, then $p^{O_p(\binom{2n}{n})} \leq 2n$.
The number of primes dividing $\binom{2n}{n}$ is at least $\frac{\log_2{\binom{2n}{n}}}{\log_2(2n)}$
For all $n\geq 2,\ \prod_{p\leq n}p \leq 4^n $ where the product is over primes.

The First

Alright, so let's get into it. We have some conditions we need to state, so... $n\geq 3$ and $\frac{2n}{3} \lt p \leq n$. Firstly, notice $$ \binom{2n}{n} = \frac{(2n)!}{n!(2n-n)!} = \frac{(2n)!}{(n!)^2} = \frac{2n(2n-1)\cdots n+1}{n(n-1)\cdots 1}.$$ I want to talk about the conditions now, this will highlight where $p$ appears in the factorials.

Notice how $p \gt \frac{2n}{3}$? Well, if we multiply by two we can see that $2p > \frac{4n}{3} > n$, therefore there's no $2p$ in $n!$ and also since $p \leq n$ then $2p\leq 2n$. So, $2p$ is in the upper half of $(2n)!$ but is not in $n!$.

Quickly, I must also address the other condition that $n\geq 3$ because if we multiply $\frac{2n}{3} \lt p \leq n$ by three, we get $2n \lt 3p \leq 3n$, therefore, $3p$ or greater will not be a factor in $(2n)!$.

All together now. We conclude there is one factor of $p$ in $2n(2n-1)\cdots n+1 $ and one factor of $p$ in $n!$. Now, consider the equation for $\binom{2n}{n}$. The factors in the numerator and denominator must now cancel out, therefore there is no such $p$ that divides $\binom{2n}{n}$.

This also shows that there are no prime factors greater than $2n$ because they'd have to divide $2n!$.

The Second - ($p \mid \binom{2n}{n} \implies p^{O_p\left(\binom{2n}{n}\right)} \leq 2n$)

In order to prove this, I need to get you up to speed on this $O_p$ function. So...
$O_p(n!)$ is a function that takes two things. A factorial and a $p$. It outputs the largest power of $p$ that divides $n!$.

For example, $O_3(6!) = 2$ as you can see in its prime factorization $6! = 2^4 \cdot 3^2 \cdot 5^1$. The actual function is described as $$ O_p(n!) = \sum_{i=1}^{\infty} \left\lfloor\frac{n}{p^i}\right\rfloor $$ Using similar logic as The First you can see that there's at least one factor of $p$ in $n!$ but there are $\lfloor\frac{n}{p}\rfloor$ factors for each multiple of $p$ in ${1,...,n}$. Now you just need to account for each multiple of $p^2, \ p^3, \ \cdots $.

Now I just want to highlight some properties of this function which are easy to verify (Hint: look at the factorizations of a,b). They are, $$O_p(ab) = O_p(a) + O_p(b) $$ $$ O_p(a/b) = O_p(a) - O_p(b) $$

Okay, now we're ready to take a look at the lemma. First, let $r(p)$ be the maximal integer exponent so that $p^{r(p)}$ doesn't step over $2n$. Formally, $p^{r(p)} \leq 2n \lt p^{r(p) + 1}$. Now, by using the properties of $O_p(n!)$ we just discussed, it follows that $$ O_p\left(\binom{2n}{n}\right) = O_p((2n)!) - 2 O_p(n!) = \sum_{i=1}^{r(p)}\left\lfloor\frac{2n}{p^i}\right\rfloor - 2 \sum_{i=1}^{r(p)}\left\lfloor\frac{n}{p^i}\right\rfloor $$

$$ \sum_{i=1}^{r(p)}\left(\left\lfloor\frac{2n}{p^i}\right\rfloor - 2\left\lfloor\frac{n}{p^i}\right\rfloor\right) \leq r(p) $$ The last line here is justified because for all real $x$, $0 \leq \lfloor 2x\rfloor - 2\lfloor x\rfloor\ \leq 1$, so the sum cannot be greater than $r(p)$ because for each iteration you contribute at most $1$. Therefore we have now shown that $$ p^{O_p\left(\binom{2n}{n}\right)} \leq p^{r(p)} \leq 2n.$$

The Third - At least $\frac{\log_2{\binom{2n}{n}}}{\log_2(2n)}$ primes divide $\binom{2n}{n}$

Alright, if you understand everything else, this should be painless.

Let $p_1, ..., p_\ell$ be the distinct primes dividing $\binom{2n}{n}$. It follows that $$ \binom{2n}{n} = \prod_{i=1}^{\ell}p^{O_p\left(\binom{2n}{n}\right)} $$ And then using The Second fact, that $p^{O_p\left(\binom{2n}{n}\right)} \leq 2n$, the max this product could be is $(2n)^\ell$. So,

$$ \binom{2n}{n} = \prod_{i=1}^{\ell}p^{O_p\left(\binom{2n}{n}\right)} \leq (2n)^\ell$$ Well, if we take the $\log_2$ of both sides we get $$\log_2\binom{2n}{n} \leq \ell\log_2(2n)$$ So yeah, just divide both sides by $\log_2(2n)$ and $$ \ell \geq \frac{\log\binom{2n}{n}}{\log_2(2n)}. $$

The Fourth - $ n\geq 2,\ \prod\limits_{p\leq n}p \leq 4^n $

Next up, we have some cool stuff. A proof by induction, everyone's favorite right?

First I'm gonna give you the base case, when $n = 2, \ \prod_{p\leq 2}p = 2 \leq 4^2$. Simple. Next I'm going to split this baby in half. Assume the inductive hypothesis works for $n-1$, now, when $n$ is even, $$ \prod_{p\leq n-1}p = \prod_{p\leq n}p \leq 4^{n-1} \lt 4^n$$ This works because $p\gt 2$ have to be odd, so you add nothing to the product when you increment by one. And then of course we assume the inductive hypothesis to be true for $n-1$. Cool, so this works for when $n$ is even. Now, what about when $n$ is odd? A little bit harder...

When $n$ is odd, we work with $n = 2m+1$. So we can just split up the product as $$ \prod_{p\leq n}p = \prod_{p\leq m+1}p \prod_{m+2\leq p \leq 2m+1}p $$ Keep this in mind. As of now we can write $$ \prod_{p\leq n}p \leq \prod_{p\leq m+1}4^{m+1} \prod_{m+2\leq p \leq 2m+1}p $$ because of the induction hypothesis and the fact that $m+1 \leq 2m = n-1$. Now we just have to rewrite the other product of $p$.

Observe that $$ \binom{2m+1}{m} = \frac{(2m+1)!}{m!(m+1)!} = \frac{(2m+1)(2m)\cdots(m+1)}{(m+1)!} = \frac{(2m+1)(2m)\cdots(m+2)}{m!}$$ So now you can see that all the primes between $m+2$ and $2m + 1$ divide $\binom{2m+1}{m}$. Since we're multiplying them in the previous product, we can now say that $$ \prod_{p\leq n}p \leq 4^{m+1}\binom{2m+1}{m}.$$ This is pretty good, but it's not what we want yet...

For an instant here, suppose with me that our beloved $\binom{2m+1}{m} \geq 2^{2m}$. Then, since $2m + 1$ is odd, we get another proof by Just Look At Pascals Triangle. Every other row has the two repeat middle values, so $$ \binom{2m+1}{m} + \binom{2m+1}{m+1} = 2\binom{2m+1}{m} \gt 2(2^{2m}) = 2^{2m+1}$$ But wait, by the binomial theorem, $$ 2^{2m+1} = \sum_{i=1}^{2m+1}\binom{2m+1}{i}$$ So darn, by contradiction, $\binom{2m+1}{m} \leq 2^{2m}$. But wait, this is good... we can add this to our product! and would you look at that... $$ \prod_{p\leq n}p \leq 4^{m+1}2^{2m} = 4^{2m+1} = 4^n$$ yesss, this concludes the proof by induction. Pretty good, right?

The Finale - Let loose

Alright, we're pretty much here. We now begin the proof.

By contradiction, assume that the postulate is not true, so $n \geq 3$ and there is no prime $p$ with $n \lt p \leq 2n$. We can use this assumption along with some others to show that $$ \binom{2n}{n} \leq (2n)^{\sqrt{2n}} \prod_{\sqrt{2n}\lt p \leq \frac{2}{3}n}p $$ This is true because of a few things. First, is $$ \binom{2n}{n} = \prod_{p\lt \sqrt{2n}}p \prod_{p\geq \sqrt{2n}}p $$ The $\sqrt{2n}$ choice seems sort of arbitrary, but follow me. We can see that $\binom{2n}{n}$ has at most $\sqrt{2n}$ prime factors that don't exceed $\sqrt{2n}$ and since we proved that the most a $p$ can contribute to $ \binom{2n}{n}$ is $2n$, the most $\sqrt{2n}$ primes can contribute is $(2n)^{\sqrt{2n}}$. Then, we know from The First that there are no $p$ such that $\frac{2n}{3} \lt p \leq n$ in $\binom{2n}{n}$, and that there are no prime factors of $\binom{2n}{n}$ greater than $2n$. Therefore, we can stop the product of primes at $\frac{2n}{3}$. Slick.

So now we have this ugly thing, let me clean it up a tiny bit. Since this inequality is saying the R.H.S is greater, we can just let the range be larger and it's still true, right? So, just get rid of the $\sqrt{2}$ there. $$ \binom{2n}{n} \leq (2n)^{\sqrt{2n}} \prod_{p\leq\frac{2}{3}n}p $$ And would you look at that, we have a product of $p$, and didn't The Fourth tell us a bound on the product of primes? Yup, it's $4^n$. So, $$ \binom{2n}{n} \leq (2n)^{\sqrt{2n}} 4^{\frac{2}{3}n} $$ BUT WAIT!!!!

In the very beginning we say that $$ \frac{4^n}{2n+1} \leq \binom{2n}{n} $$ and I have just shown that if there is no $p$ such that $n \lt p \lt 2n$ where $n \geq 3$, that $$\binom{2n}{n} \leq (2n)^{\sqrt{2n}} 4^{\frac{2}{3}n}$$ So it must be true that $$ \frac{4^n}{2n+1} \leq (2n)^{\sqrt{2n} 4^{\frac{2}{3}n}} $$ BUT believe it or not! This inequality fails with a whopping $ n \geq 468 $! That's a 279 digit number on the R.H.S! So now we can just see that $$ 2, 3, 5, 7, 9, 11 , 13, 23, 43, 83, 163, 317, 631 $$ satisfy the postulate for $ n \lt 468 $.

Therefore by contradiction and evaluation, there must exist some $p$ such that $n \lt p \lt 2n$ where $ n \geq 3$. Wow.

Afterward

I still can't believe Erdős came up with it when he was 20! I remember spending numerous hours bashing my head against the wall just trying to figure his proof out. I think a part of this is because, at the time, I had never really read a solid proof that wasn't just some cookie cutter example of a proof technique. Most proofs that I ran into during college were no longer than a page and were built almost strictly on already known, recently taught theorems.

Another reason why this was so hard for me to parse is because Erdős seems to say true things that aren't immediately obvious. Then somehow, all this seemingly random information about the middle binomial coefficient, prime factorizations, etc... comes together to show that some random inequality creates a contradiction. This showed me where there was unintuitive deep connection that I would have never seen otherwise. This is why I've gone and fleshed out his proof into pieces that I find a lot easier to consume, because this is very worth sharing.

At the end of the day, this is all fun and makes sense, but I applaud Erdős on whatever it was that allowed him to make such good connections. Obviously his understanding was much greater than mine!!

Cool Applications

Here are some cool googleable applications that I thought I'd mention

The set of integers $\lbrace1, 2, 3, ..., 2n\rbrace $ can be partitioned into $n\geq 1$ pairs $\lbrace a_i,b_i\rbrace$ such that $a_i + b_i$ is prime for all $i = 1, ..., n$.
There are infinitely many $G_{2n}$'s that have a Hamiltonian cycle.
The $n\gt 1$'th harmonic number, $ H_n = \sum_{k=1}^{n}\frac{1}{k}$, is never an integer.

Bertrand's Postulate - 2025-03-30