Bertrand's Postulate - 2025-03-30

Bertrand's Postulate --- !!! Proof Under Construction !!!

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$.
All prime factors of $\binom{2n}{n}$ are at most $2n$.

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}$.

The Second

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 this 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 is why I've gone and fleshed out his proof into pieces that I find a lot easier to consume.

At the end of the day, this is all fun and makes sense. But I have a hard time understanding how Erdős thought to glue these facts together to create this proof. Obviously his understanding was much greater than mine!!