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.