Bertrand's Postulate Part 4: The Proof

Click here to see part 1 of this four week series.

Click here to see part 2 of this four week series.

Click here to see part 3 of this four week series.

This is the final post in my four week series on Bertrand's Postulate. Using the information we have discussed in the last three weeks, we will officially prove that there is always a prime between a number and its double.

This final step five is the step that will complete the upper bound and provide the proof. Since we have restricted the values of the prime factors so much over the last four steps, we will be able to utilize a technique called proof by contradiction. Last week, we did a proof by induction where we assumed the conclusion was true and did the math from there. With a proof by contradiction, one assumes that the conclusion is false and will later run into a problem.

To prove Bertrand’s Postulate, we will assume that there are no primes between n and 2n. So, this means that there are no prime factors that are:

• greater than 2n by step 2
• equal to 2n because 2n is even, and therefore, not prime
• between n and 2n because of our assumption
• between ⅔n and n by step 1

This means that all prime factors of “2n choose n” are less than ⅔n.

Keep in mind that this does not include prime powers. We did prove that there are no prime powers greater than 2n, but they can exist below that. So, an upper bound on each prime power would be 2n.

We know that (√(2n))² is 2n. So, any number greater than √(2n) cannot have a prime power factor. If it did, then the factor would be greater than 2n, which is impossible (see step two). This means that there are at most √(2n) values of 2n (the maximum of a prime power) in the prime factorization of “2n choose n.” So, we can set an upper bound on any prime factor below √(2n) as 2n^√(2n).

But there can still be prime factors between √(2n) and ⅔n. They just will have an exponent of one. So, the product of all the primes between √(2n) and ⅔n will cover everything in that interval, since there are no exponents. To make the math simpler, we will just use (⅔n)╫. Multiplying these two quantities together will yield an upper bound on “2n choose n.”

“2n choose n” < 2n^√(2n) • (⅔n)╫

In step 4, we set an upper bound on that primorial. (⅔n)╫ is definitely less than 4^⅔n. So, we can plug that into the right-hand side to get:

“2n choose n” < 2n^√(2n) • 4^⅔n

Also, a lower bound was set on “2n choose n” in step 3. We know that it can’t be smaller than 4ⁿ/2n. Plug that into the left-hand side to get:

4ⁿ/2n < 2n^√(2n) • 4^⅔n

And now, we are at an equation that can be solved with algebra! Simplifying this takes a lot of logarithms and complicated graphing, but it will end up as:

n < 468

That means that any time n is bigger than 468, the bounds that were created after assuming that there are no primes between n and 2n will not work. This means that there must be a prime between n and 2n every time n is greater than 468 because any other possibility was proven impossible.

The only time where it is theoretically possible for an n value to have no prime between n and 2n is when n is less than 468. But, it was mentioned before that Joseph Bertrand himself found a prime for all n values up through three-million. So, there can’t be a number less than 468 that the postulate doesn’t work for. And thus, Bertrand’s Postulate is proven.

Personally, I do think this proof is really cool. However, it is difficult to be as engaged when it takes four fairly long posts to prove. But what I find more interesting than the actual mathematical side of it is that it is understandable to just someone with a couple years of high school mathematics. I did categorize these posts with the other advanced ones, but there is no need for calculus or even much precalculus to understand (the only precalculus is really the logarithms that I left out at the end). The real barrier in understanding them is the notation that mathematicians use. The actual paper used much more complex language as well as things like sigma notation that wouldn't make as much sense initially to a high school student. But after that language is translated into something simpler, the content itself is certainly understandable and even quite interesting. I am looking forward to making more of these series with other mathematical papers in the months to come.

Bertrand's Postulate Part 3: Bounding the Central Binomial Coefficient

Click here to see part 1 of this four week series.

Click here to see part 2 of this four week series.

This is week three of the four week series on Bertrand's Postulate. Last week, we restricted the range of the prime factors of "2n choose n." This week, we are going to restrict the size of it. This will use many of the techniques and identities we have discussed in the last two weeks to do.

The third step here is to determine the lower bound. The fourth step will be to find the upper bound, and we will then have an inequality to work with. To find a lower bound, we must use another property of Pascal’s Triangle.

1

1          1

1          2          1

1         3         3         1

1        4        6        4        1

1       5      10      10      5       1

1      6       15     20     15       6      1

1     7      21     35     35     21      7      1

1     8     28     56     70     56     28     8     1

1    9    36     84    126   126    84     36    9    1

1   10   45   120   210   252   210   120   45   10   1

We will now expand a few polynomials (see definition of polynomial expansion in the first post). The Pascal’s Triangle application will become clear in a minute.

(a + b)⁰ = 1
(a + b)¹ = 1a + 1b
(a + b)² = 1a² + 2ab + 1b²
(a + b)³ = 1a³ + 3a²b + 3ab² + 1b³
(a + b)⁴ = 1a⁴ + 4a³b + 6a²b² + 4ab³ + 1b⁴

Do you see a pattern? Let me make it clearer:

                     (a + b)⁰ = 1
                (a + b)¹ = 1a  +  1b
           (a + b)² = 1a² +  2ab  + 1b²
         (a + b)³ = 1a³ + 3a²b + 3ab² + 1b³
(a + b)⁴ = 1a⁴ + 4a³b + 6a²b² + 4ab³ + 1b⁴

The coefficients in each expansion are the numbers in the corresponding row of Pascal’s Triangle. In general, by using the “n choose k” notation, this theorem can be generalized as:

(a + b)ⁿ = (“n choose 1”)aⁿ + (“n choose 2”)a^n-1b + (“n choose 3”)a^n-2b²... + (“n choose n-1”)ab^n-1 + (“n choose n”)bⁿ

After you let that sink in for a second, the process of creating the lower bound will be simple.

The lower bound that is used is 4ⁿ/2n. To prove that this is a lower bound, we must prove the following inequality to be true:

4ⁿ/2n < “2n choose n”

This can be rearranged to be:

4ⁿ < 2n(“2n choose n”)

4ⁿ can be rewritten using the binomial theorem. A lone four is not an expandable binomial, but here is a reconfiguration of 4ⁿ that can be expanded.

4ⁿ
(2²)ⁿ
2²ⁿ
(1 + 1)²ⁿ 

Plug these values into the binomial theorem for a, b, and n to get:

(a + b)ⁿ = (“n choose 1”)aⁿ + (“n choose 2”)a^n-1b + (“n choose 3”)a^n-2b²... + (“n choose n-1”)ab^n-1 + (“n choose n”)bⁿ

(1 + 1)²ⁿ = (“2n choose 1”)1²ⁿ + (“2n choose 2”)1^2n-11 + (“2n choose 3”)1^2n-21²... + (“2n choose 2n-1”)1•1^2n-1 + (“2n choose 2n”)1²ⁿ

Since one raised to any power is one, all of the ones cancel out to get:

(1 + 1)²ⁿ = (“2n choose 1”)1 + (“2n choose 2”)1 + (“2n choose 3”)1 ... + (“2n choose 2n-1”)1 + (“2n choose 2n”)1

(1 + 1)²ⁿ = (“2n choose 1”) + (“2n choose 2”) + (“2n choose 3”) ... + (“2n choose 2n-1”) + (“2n choose 2n”)

This creates just a sum of all of the values in the (2n)-th row of Pascal’s Triangle. Earlier, it was noted that the central binomial coefficient of a row is the largest number in that row. So, “2n choose n” is the largest number in the sum above.

How many numbers are in that sum? Since it is the (2n)-th row of Pascal’s Triangle, there are 2n entries in that row. This means that the product of 2n and “2n choose n” must be greater than that sum.

(“2n choose 1”) + (“2n choose 2”) + (“2n choose 3”) ... + (“2n choose 2n-1”) + (“2n choose 2n”) < 2n(“2n choose n”)

What is that sum equal to? It was defined to be the expansion of 4ⁿ, meaning that 4ⁿ can be substituted in for that sum.

4ⁿ < 2n(“2n choose n”)

Dividing both sides by 2n gives the inequality that the step was looking for:

4ⁿ/2n < “2n choose n”

And that completes the step.

The fourth step is to set an upper bound. A lower bound won’t do much good without an upper bound to counter it. A fully intact upper bound for “2n choose n” cannot be found until step five is partly established, but an upper bound can be placed on a different expression which will play back into the proof later on.

This step requires something called the primorial function, which is similar to the factorial function. The number n factorial is the product of all of the positive integers less than or equal to n. Similarly, the number n primorial (written n╫) is the product of all of the prime numbers less than or equal to n. For example:

4╫ = 3 • 2 = 6
8╫ = 7 • 5 • 3 • 2 = 210
16╫ = 13 • 11 • 7 • 5 • 3 • 2 = 30030

This step will set an upper bound on the number n╫. The upper bound we will try to set is 4ⁿ. So, this is the inequality that needs to be proven:

n╫ < 4ⁿ 

This proof needs to be tackled in two parts. First, it needs to be proven for all odd values of n. Then, it can be proven for all even values of n.

If n is odd, then it can be rewritten as 2m + 1 assuming that m is an integer (see definition of odd number). Throughout the proof, quantities like “2n choose n” and “2m choose m” have come up, but the row of Pascal’s Triangle it refers to is always an even numbered row (2n and 2m are even). What about odd numbered rows?

1

1          1

1          2          1

1         3         3         1

1        4        6        4        1

1       5      10      10      5       1

1      6       15     20     15       6      1

1     7      21     35     35     21      7      1

1     8     28     56     70     56     28     8     1

1    9    36     84    126   126    84     36    9    1

1   10   45   120   210   252   210   120   45   10   1

An odd numbered row does not have a center position, but the two positions in the middle are always equal to each other. In other words, “2m+1 choose m” is equal to “2m+1 choose m+1.”

“2m+1 choose m” = “2m+1 choose m+1”

Now, add “2m+1 choose m” to both sides of this.

“2m+1 choose m” = “2m+1 choose m+1”
“2m+1 choose m” + “2m+1 choose m” = “2m+1 choose m+1” + “2m+1 choose m”
2(“2m+1 choose m”) = “2m+1 choose m+1” + “2m+1 choose m”

The right hand side of that equation can be thought of as the sum of two of the elements of the (2m+1)-st row of Pascal’s Triangle. But, what if the sum of all of the elements in the (2m+1)-st row was found? That would definitely be a bigger number than what is currently there. So, an inequality can be formed using that sum as the right-hand side.

2(“2m+1 choose m”) < (“2m+1 choose 1”) + (“2m+1 choose 2”) + (“2m+1 choose 3”) ... + (“2m+1 choose 2m”) + (“2m+1 choose 2m+1”)

But in step 3, we defined this to be the polynomial expansion of (1 + 1)^2m+1, or 2^2m+1. Substitute that in for the right-hand side. Then, use the laws of exponents (see definition of law of exponents) to get:

2(“2m+1 choose m”) < 2^2m+1
(“2m+1 choose m”) < 2^2m+1 ÷ 2¹
(“2m+1 choose m”) < 2^2m+1–1
(“2m+1 choose m”) < 2^2m
(“2m+1 choose m”) < (2²)^m
(“2m+1 choose m”) < 4^m

Now, let’s look at the prime factorization of “2m+1 choose m.” Recall the formula that was used to find exponents of primes in step 1 and step 2.

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)

This can be rewritten for the quantity “2m+1 choose m” fairly easily.

v_p(“2m+1 choose m”) = v_p((2m + 1)!) - 2v_p(m!) - v_p(m + 1)

Prime numbers less than m+1 are difficult to analyze, but what about between m+2 and 2m+1? By similar logic as in step 1, all of these numbers will have an exponent of zero in m! or (m+1)!, but an exponent of one in (2m+1)!. So, it can be guaranteed that each prime between m+2 and 2m+1 is a factor of “2m+1 choose m.” This also means that the product of all primes between m+2 and 2m+1 is less than or equal to “2m+1 choose m.”

The inequality we are trying to reach is n╫ < 4ⁿ. So, plugging that inequality in on a different interval (say (m+1)╫ < 4^m+1), is a legal maneuver. This is called proof by induction.

(m+1)╫ < 4^m+1

The left-side of the inequality above is (m+1)╫. It was just determined what the upper bound of the product of all primes between m+2 and 2m+1 was as well. If we multiply the primorial of m+1 by the product of primes between m+2 and 2m+1, we will just get the primorial of 2m+1. This number will be less than the product of the two right hand sides.

(2m+1)╫ < 4^m+1 • “2m+1 choose m”

Earlier, it was proven that “2m+1 choose m” has an upper bound of 4^m. Since that will only make the right side bigger, we can plug that in without a problem. This gives:

(2m+1)╫ < 4^m+1 • 4^m

Using the law of exponents brings it to:

(2m+1)╫ < 4^2m+1

And substituting n back in for 2m+1 gives:

n╫ < 4ⁿ 

We are almost done with the step. The hard part is complete; any odd values of n are covered. All that needs to be done is to make sure the even values are covered as well.

If n is even, then its primorial will always be equal to the odd number below it. For instance:

4╫ = 6 = 3╫
10╫ = 210 = 9╫
22╫ = 9699690 = 21╫

This is because that even number cannot be prime. If n is even, its primorial must be equal to (n-1)╫ because n-1 is the highest potentially prime number less than n.

n╫ = (n-1)╫

Earlier, it was proved that the upper bound works on an odd numbered primorial. Since n-1 is odd, we can plug that in to get:

(n-1)╫ < 4^n–1

We just determined that n╫ = (n-1)╫, so substituting n╫ in for (n-1)╫ gives:

n╫ < 4^n–1

4^n–1 is definitely less than 4ⁿ, so that can be put on the right-hand side to get:

n╫ < 4ⁿ

Since the bound is good on all odd numbers and all even numbers, the step is complete.

We have most of the groundwork done. Next week, we will officially prove Bertrand's Postulate as well as finalize our upper bound.

Bertrand's Postulate Part 2: Restricting the Factor Domain

Click here to see part one of this four week series.



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.

To prove this, we first need to go over the definition of factorials.

The number n factorial (written n!) is the product of all of the positive integers less than or equal to n.

For example, 4! = 4 • 3 • 2 • 1 = 24. 7! = 7 • 6 • 5 • 4 • 3 • 2 • 1 = 5040.

How do factorials play into this proof? Well, assuming that the prime 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 2p also must be less than n. But, what happens when we multiply the inequality by two?

⅔n < p < n
2(⅔n) < 2p < 2n
1⅓n < 2p < 2n

This means that 2p 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 (2n)!.

A simpler way to write “number of times a prime factor appears in a number” would be to use the following notation:

v_p(x)

Assume that p is the prime number and x is the number that the prime is a factor of. For example:

v₂(24) = 3
v₅(50) = 2
v_p((2n)!) = 1
v_p((2n)!) = 2

There exists a formula that enables one to find the number of times a certain prime factor appears in the factorization of a quantity like “2n choose n.” For that example, the formula goes:

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)

The values of 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 (2n)! nonetheless. It appeared in n! once and (2n)! twice. So, those values can be substituted in to see how many p’s can be in “2n choose n.”

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)
v_p(“2n choose n”) = 2 - 2(1)
v_p(“2n choose n”) = 2 - 2
v_p(“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.

This step will require another definition, but this one is extremely simple. The name of it makes it sound much more complicated than it is.

A number’s floor function is the greatest integer less than or equal to that number. For example:

floor(7.5) = 7
floor(18) = 18
floor(π) = 3

These floor functions play a role in Legendre’s Theorem (created by Adrien-Marie Legendre), which is used in the proof of step two. Legendre’s Theorem states that to find the prime factorization of n!, one simply plugs prime numbers into the following formula, which will find their exponent.

v_p(n!) = floor(n/p) + floor(n/p²) + floor(n/p³) + floor(n/p⁴) + ...

For example, let’s find the exponent of 2 in the number 4! = 24.

v_p(n!) = floor(n/p) + floor(n/p²) + floor(n/p³) + floor(n/p⁴) + ...
v₂(4!) = floor(4/2) + floor(4/2²) + floor(4/2³) + floor(4/2⁴) + ...
v₂(4!) = floor(4/2) + floor(4/4) + floor(4/8) + floor(4/16) + ...
v₂(4!) = floor(2) + floor(1) + floor(0.5) + floor(0.25) + ...
v₂(4!) = 2 + 1 + 0 + 0 + ...
v₂(4!) = 3

Let’s return to the formula we used in the last step to find the exponent on a prime factor of “2n choose n.”

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)

It is impossible to use logic to define the exponent on primes greater than 2n for the terms in this formula. However, we can use Legendre’s Theorem to determine the exponent on prime factors of n! and (2n)!.

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)
v_p(“2n choose n”) = [floor(2n/p) + floor(2n/p²) + ...] - 2[floor(n/p) + floor(n/p²) + ...]

Though 2n cannot be plugged in for p (2n is even, and therefore is not prime), but any number larger than 2n 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 (2n divided by a number larger than 2n 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_p(“2n choose n”) = 0 - 2(0)
v_p(“2n choose n”) = 0 - 0
v_p(“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.

Bertrand's Postulate Part 1: Definitions, History, and an Introduction

Today, I am beginning a four-post series on the proof to Bertrand's Postulate. This postulate asks the following question: is there always a prime number between a number and its double. For instance, the number 3 doubled is 6, and 5 is prime. The number 4 doubled is 8, and 7 is prime. Number theorists wondered if this would work forever.

The proof for this is written up on wikipedia in a pretty short text, but it has lots of advanced notating and vocabulary. I could tell when reading it that the proof itself was not above my head, but the article was still extremely difficult to understand. So, I made it a project for myself to decode that article, and I eventually figured it out. Since it is a pretty cool proof when explained in a simpler way, I decided to share it. It is a long one, which is why I am breaking it into four parts. I am also making sure that we have most of the necessary knowledge covered in this post so that we can continue on. Some of the information discussed in each post is also interesting on its own, so don't stress out if you can only follow pieces of the proof. I can barely follow parts of it as well.

First, here are some definitions to make sure you understand:

Integer: a number that can be defined as positive, negative, or zero (e.g. 3, -2, and 0 are integers; 2.4 and π are non-integers)

Even Number: a number that is a multiple of two (written as 2m)

Odd Number: one more than an even number (written as 2m + 1)

Sum: the answer to an addition problem (e.g. the sum of 2 and 7 is 9)

Product: the answer to a multiplication problem (e.g. the product of 3 and 5 is 15)

Prime Number: a number that is only divisible by one and itself

Prime Power: a number that is a positive integer power of a single prime number

Factor: a number that evenly divides into another number (e.g. 6 is a factor of 18; 3 is a prime factor of 12)

Prime Factorization: the decomposition of a number into a product of its prime factors (e.g. 4680 = 2³ • 3² • 5 • 13)

Polynomial Expansion: a polynomial’s expansion is a way to write the polynomial such that it is a sum of products (e.g. 2(x - 7) has a polynomial expansion of 2x - 14)

Law of Exponents: the expression a^p • a^q can be simplified to a^p+q, or similarly, the expression a^p ÷ a^q can be simplified to a^p–q, or the expression (a^p)^q can be simplified to a^pq

Also, for some historical context, here are some of the mathematicians that had an influence on this postulate:

Joseph Louis François Bertrand - born March 11, 1822 in Paris, France; died April 5, 1900 in Paris, France. Bertrand was a professor at the École Polytechnique and Collège de France and was known for his contributions to number theory, differential geometry, probability theory, economics, and thermodynamics. He was the first to conjecture Bertrand’s Postulate, and confirmed by hand the first three-million values of n.

Pafnuty Lvovich Chebyshev - born May 16, 1821 in Okatovo, Russia (near Moscow); died December 8, 1894 in St. Petersburg, Russia. Chebyshev was a professor at St. Petersburg University, and was known for his contributions to probability, statistics, mechanics, and number theory. In 1850, he was the first to prove Bertrand’s Postulate, which gave the theorem nicknames such as the “Bertrand-Chebyshev Theorem” or “Chebyshev’s Theorem.”

Srinivasa Ramanujan - born December 22, 1887 in Erode, India (near Chennai); died April 26, 1920 in Chennai, India. Though an autodidact, Ramanujan is said to be one of the best mathematicians of all time, making a remarkable impact in mathematical analysis, number theory, infinite series, and continued fractions. Using properties of the Gamma Function (a function commonly used in statistics and combinatorics), Ramanujan was able to provide a simpler version of Chebyshev’s proof in 1919.

Paul Erdös - born March 26, 1913 in Budapest, Hungary; died September 20, 1996 in Warsaw, Poland. Erdös spent his life traveling from university to university collaborating with different professors on problems in fields such as combinatorics, graph theory, number theory, set theory, and probability theory. He was known for finding extremely elementary proofs for various conjectures, which he did with Bertrand’s Postulate in 1934.

Blaise Pascal - born June 19, 1623 in Clermont-Ferrand, France; died August 19, 1662 in Paris, France. In addition to his accomplishments in number theory, projective geometry, probability theory, and economics, Pascal was a physicist, philosopher, theologist, and the inventor of the first digital calculator. He is possibly best known for popularizing Pascal’s Triangle, which plays a role in Erdös’s proof of Bertrand’s Postulate.

Adrien-Marie Legendre - born September 18, 1752 in Paris, France; died January 10, 1833 in Paris, France. Legendre was a professor at the École Militaire and École Normale, and was known for his contribution to number theory, elliptic functions, calculus, and applied mathematics. He created the formula to find the frequency of prime factors in factorials, which is now often called Legendre’s Theorem.

I'm sure there are more, but those six were some of the most prominent. Now, let's begin to tell the tale of proving Bertrand's Postulate.

In 1845, Joseph Bertrand proposed the idea that there will always be a prime number between a number and its double, or n and 2n. Bertrand had already checked by hand every number between two and three-million and found that they all fit this hypothesis. But, numbers are infinite, and people can’t go checking every single one. This is why a mathematical proof would be needed to verify this conjecture and turn it into a theorem.

Pafnuty Chebyshev offered a full mathematical proof of this statement in 1850; he used logic and mathematics to prove that any value of n would have a prime between it and its double. A simpler proof was offered in 1919 by Srinivasa Ramanujan, and an even simpler one was demonstrated by Paul Erdös in 1934. A quote commonly attributed to Erdös is:

Chebyshev said it, but I’ll say it again

There is always a prime between n and 2n.

To understand Erdös’s proof, it is important to first know a few properties of Pascal’s Triangle, which was popularized by Blaise Pascal. Pascal’s triangle starts with a triangular formation of ones.

1

1  1

1     1

1        1

1           1

To fill in a blank space in this triangle, one then must add the two numbers above it. For instance, the space in the third row between the two ones would be filled in by adding the 1 above and to the left and the 1 above and to the right. 1 + 1 = 2, so this space would have a 2 in it.

1

1  1

1  2  1

1        1

1           1

Similarly, the square underneath the 1 and the 2 can be filled in with a 3.

1

1  1

1  2  1

1  3     1

1           1

By continuing this process, the triangle can be extended infinitely.

1

1          1

1          2          1

1         3         3         1

1        4        6        4        1

1       5      10      10      5       1

1      6       15     20     15       6      1

1     7      21     35     35     21      7      1

1     8     28     56     70     56     28     8     1

1    9    36     84    126   126    84     36    9    1

1   10   45   120   210   252   210   120   45   10   1

With this triangle, each number can be defined by saying its row number and what position it is in in that row. Since the ones are the base of the triangle, and are not necessarily part of it, the top row is defined to be row zero and the left-most element in each row is element zero. By keeping this in mind, any number in Pascal’s Triangle can be quickly found. For example, the fifth element of row seven would be 21.

Rather than going through the process of saying “the kth element of row n in Pascal’s Triangle,” mathematicians will often use the notation “n choose k,” with n being the row number and k being the number’s position in the row. For instance, “6 choose 2” = 15.

In Pascal’s Triangle, there are some numbers that stick out because they are in the center of their row. For instance:

1

1          1

1          2          1

1         3         3         1

1        4        6        4        1

1       5      10      10      5       1

1      6       15     20     15       6      1

1     7      21     35     35     21      7      1

1     8     28     56     70     56     28     8     1

1    9    36     84    126   126    84     36    9    1

1   10   45   120   210   252   210   120   45   10   1

These numbers have a very simple notation in the “n choose k” format because k is half of n. Since n and k can never be fractions (there is no 2.7th element in a row), the best way to write these numbers is “2n choose n.” Mathematicians call these numbers as central binomial coefficients. Note that the central binomial coefficient is the largest number in each row of the triangle.

These central binomial coefficients play a huge role in Erdös’s proof. What Erdös actually proved was that there is always a prime between n and 2n that is a prime factor of the corresponding central binomial coefficient: “2n choose n.” 

Next week, I will continue on and show some of the first steps of the actual proof.