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 2

*n*.

The proof utilizes the central binomial coefficients that I explained last week, each one being written in the form "2

*n*choose

*n*." The final conclusion actually states that every number of the form "2

*n*choose

*n*" has a prime factor between

*n*and 2

*n*. By determining this, we will then be able to say that there must always then be a prime between

*n*and 2

*n*. But how do we prove that?

This week, we will look at how to limit the range of possible prime factors of "2

*n*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 2

*n*. Next week, we will set a lower and upper bound on the size of "2

*n*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 2

*n*. So let's get to it!

The first step is to prove that none of the prime factors of “2

*n*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 2

*n*.

*n*factorial (written

*n*!) is the product of all of the positive integers less than or equal to

*n*.

*p*is between ⅔

*n*and

*n*,

*p*will only appear once in the prime factorization of

*n*!. This is because

*n*! only has prime factors that are less than

*n*. For

*p*to have been multiplied in twice, that means 2

*p*also must be less than

*n*. But, what happens when we multiply the inequality by two?

*n*<

*p*<

*n*

2(⅔

*n*) < 2

*p*< 2

*n*

1⅓

*n*< 2

*p*< 2

*n*

*p*is at least 1⅓

*n*, which cannot be a factor of

*n*!. So, a factor of

*p*can only appear once. By similar logic, there are two factors of

*p*in (2

*n*)!.

*v*

*(*

_{p}*x*)

*p*is the prime number and

*x*is the number that the prime is a factor of. For example:

*v*

_{2}(24) = 3

*v*

_{5}(50) = 2

*v*

*((2*

_{p}*n*)!) = 1

*v*

*((2*

_{p}*n*)!) = 2

*n*choose

*n*.” For that example, the formula goes:

*v*

*(“2*

_{p}*n*choose

*n*”) =

*v*

*((2*

_{p}*n*)!) - 2

*v*

*(*

_{p}*n*!)

*p*or

*n*are not defined (aside from the fact that

*p*is between ⅔

*n*and

*n*), but we just determined the number of times

*p*appeared in

*n*! and (2

*n*)! nonetheless. It appeared in

*n*! once and (2

*n*)! twice. So, those values can be substituted in to see how many

*p*’s can be in “2

*n*choose

*n*.”

*v*

*(“2*

_{p}*n*choose

*n*”) =

*v*

*((2*

_{p}*n*)!) - 2

*v*

*(*

_{p}*n*!)

*v*

*(“2*

_{p}*n*choose

*n*”) = 2 - 2(1)

*v*

*(“2*

_{p}*n*choose

*n*”) = 2 - 2

*v*

*(“2*

_{p}*n*choose

*n*”) = 0

So,

*p*appears zero times when it is between ⅔

*n*and

*n*. In other words, “2

*n*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 “2

*n*choose

*n*” that are greater than 2

*n*. Furthermore, this step will also demonstrate that there are no powers of prime factors of “2

*n*choose

*n*” greater than 2

*n*. 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 2

*n*.

floor(18) = 18

floor(π) = 3

*n*!, one simply plugs prime numbers into the following formula, which will find their exponent.

*v*

*(*

_{p}*n*!) = floor(

*n*/

*p*) + floor(

*n*/

*p*

^{2}) + floor(

*n*/

*p*

^{3}) + floor(

*n*/

*p*

^{4}) + ...

*v*

*(*

_{p}*n*!) = floor(

*n*/

*p*) + floor(

*n*/

*p*

^{2}) + floor(

*n*/

*p*

^{3}) + floor(

*n*/

*p*

^{4}) + ...

*v*

*(4!) = floor(4/2) + floor(4/2*

_{2}^{2}) + floor(4/2

^{3}) + floor(4/2

^{4}) + ...

*v*

*(4!) = floor(4/2) + floor(4/4) + floor(4/8) + floor(4/16) + ...*

_{2}*v*

*(4!) = floor(2) + floor(1) + floor(0.5) + floor(0.25) + ...*

_{2}*v*

*(4!) = 2 + 1 + 0 + 0 + ...*

_{2}*v*

*(4!) = 3*

_{2}*n*choose

*n*.”

*v*

*(“2*

_{p}*n*choose

*n*”) =

*v*

*((2*

_{p}*n*)!) - 2

*v*

*(*

_{p}*n*!)

*n*for the terms in this formula. However, we can use Legendre’s Theorem to determine the exponent on prime factors of

*n*! and (2

*n*)!.

*v*

*(“2*

_{p}*n*choose

*n*”) =

*v*

*((2*

_{p}*n*)!) - 2

*v*

*(*

_{p}*n*!)

*v*

*(“2*

_{p}*n*choose

*n*”) = [floor(2

*n*/

*p*) + floor(2

*n*/

*p*

^{2}) + ...] - 2[floor(

*n*/

*p*) + floor(

*n*/

*p*

^{2}) + ...]

*n*cannot be plugged in for

*p*(2

*n*is even, and therefore is not prime), but any number larger than 2

*n*can be plugged in to see if it has a non-zero exponent. But, the first term in each of the two infinite series will end up as zero (2

*n*divided by a number larger than 2

*n*is less than one, and thus, will have a floor function of zero). Since each term in each series is shrinking, they will all end up with a floor function of zero. So, both infinite sums will simplify to zero.

*v*

*(“2*

_{p}*n*choose

*n*”) = 0 - 2(0)

*v*

*(“2*

_{p}*n*choose

*n*”) = 0 - 0

*v*

*(“2*

_{p}*n*choose

*n*”) = 0

So, all

*p*values greater than 2

*n*will have an exponent of zero, meaning that there are no prime factors of “2

*n*choose

*n*” greater than 2

*n*. This completes the second step.

Make sure to return next week so we can start to restrain the size of the number "2

*n*choose

*n*," and then we will be just inches away from the proof of Bertrand's Postulate.

## No comments:

## Post a Comment