This is week two of a four week series on the proof to Bertrand's Postulate. Last week, I went over some history and definitions pertaining to the problem, as well as introducing some facts about Pascal's triangle that come into play in the proof. This week, we can begin the actual process of proving that there is always a prime between n and 2n.
The proof utilizes the central binomial coefficients that I explained last week, each one being written in the form "2n choose n." The final conclusion actually states that every number of the form "2n choose n" has a prime factor between n and 2n. By determining this, we will then be able to say that there must always then be a prime between n and 2n. But how do we prove that?
This week, we will look at how to limit the range of possible prime factors of "2n choose n." If there are fewer possibilities of where these factors can exist on the number line, then it will be tougher (and eventually impossible) to find a number of this form without a prime factor between n and 2n. Next week, we will set a lower and upper bound on the size of "2n choose n," which will provide an inequality to work with. And in the last post, we will show that because of all of these restraints, there must be a prime between n and 2n. So let's get to it!
The first step is to prove that none of the prime factors of “2n choose n” are between ⅔n and n. By proving this, it will restrict the amount of spots for the prime factor to exist, and hopefully at some point restricting it to between n and 2n.
2(⅔n) < 2p < 2n
1⅓n < 2p < 2n
v5(50) = 2
vp((2n)!) = 1
vp((2n)!) = 2
vp(“2n choose n”) = 2 - 2(1)
vp(“2n choose n”) = 2 - 2
vp(“2n choose n”) = 0
So, p appears zero times when it is between ⅔n and n. In other words, “2n choose n” has no prime factors between ⅔n and n, thus completing this part of the proof.
The second step is to prove that there are no prime factors of “2n choose n” that are greater than 2n. Furthermore, this step will also demonstrate that there are no powers of prime factors of “2n choose n” greater than 2n. This will continue the process of restricting possible prime factors of step one, which will later make it impossible to have no prime factors between n and 2n.
floor(18) = 18
floor(π) = 3
v2(4!) = floor(4/2) + floor(4/22) + floor(4/23) + floor(4/24) + ...
v2(4!) = floor(4/2) + floor(4/4) + floor(4/8) + floor(4/16) + ...
v2(4!) = floor(2) + floor(1) + floor(0.5) + floor(0.25) + ...
v2(4!) = 2 + 1 + 0 + 0 + ...
v2(4!) = 3
vp(“2n choose n”) = [floor(2n/p) + floor(2n/p2) + ...] - 2[floor(n/p) + floor(n/p2) + ...]
vp(“2n choose n”) = 0 - 0
vp(“2n choose n”) = 0
So, all p values greater than 2n will have an exponent of zero, meaning that there are no prime factors of “2n choose n” greater than 2n. This completes the second step.
Make sure to return next week so we can start to restrain the size of the number "2n choose n," and then we will be just inches away from the proof of Bertrand's Postulate.