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 "2

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

^{0}= 1

(a + b)

^{1}= 1a + 1b

(a + b)

^{2}= 1a

^{2}+ 2ab + 1b

^{2}

(a + b)

^{3}= 1a

^{3}+ 3a

^{2}b + 3ab

^{2}+ 1b

^{3}

(a + b)

^{4}= 1a

^{4}+ 4a

^{3}b + 6a

^{2}b

^{2}+ 4ab

^{3}+ 1b

^{4}

^{0}=

**1**

(a + b)

^{1}=

**1**a +

**1**b

(a + b)

^{2}=

**1**a

^{2}+

**2**ab +

**1**b

^{2}

^{ }(a + b)

^{3}=

**1**a

^{3}+

**3**a

^{2}b +

**3**ab

^{2}+

**1**b

^{3}

(a + b)

^{4}=

**1**a

^{4}+

**4**a

^{3}b +

**6**a

^{2}b

^{2}+

**4**ab

^{3}+

**1**b

^{4}

^{}

*n*choose

*k*” notation, this theorem can be generalized as:

^{n}= (“n choose 1”)a

^{n}+ (“n choose 2”)a

^{n-1}b + (“n choose 3”)a

^{n-2}b

^{2}... + (“n choose n-1”)ab

^{n-1}+ (“n choose n”)b

^{n}

*/2*

^{n}*n*. To prove that this is a lower bound, we must prove the following inequality to be true:

*/2*

^{n}*n*< “2

*n*choose

*n*”

*< 2*

^{n }*n*(“2

*n*choose

*n*”)

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

^{n}*that can be expanded.*

^{n}

^{n}(2

^{2})

^{n}2

^{2}

^{n}(1 + 1)

^{2}

^{n}^{n}= (“n choose 1”)a

^{n}+ (“n choose 2”)a

^{n-1}b + (“n choose 3”)a

^{n-2}b

^{2}... + (“n choose n-1”)ab

^{n-1}+ (“n choose n”)b

^{n}

^{}

^{2}

*= (“2*

^{n}*n*choose 1”)1

^{2}

*+ (“2*

^{n}*n*choose 2”)1

^{2}

^{n}^{-1}1 + (“2

*n*choose 3”)1

^{2}

^{n}^{-2}1

^{2}... + (“2

*n*choose 2

*n*-1”)1•1

^{2}

^{n}^{-1}+ (“2

*n*choose 2

*n*”)1

^{2}

^{n}

^{}

^{}^{2}

*= (“2*

^{n}*n*choose 1”)1 + (“2

*n*choose 2”)1 + (“2

*n*choose 3”)1

^{ }... + (“2

*n*choose 2

*n*-1”)1 + (“2

*n*choose 2

*n*”)1

^{2}

*= (“2*

^{n}*n*choose 1”) + (“2

*n*choose 2”) + (“2

*n*choose 3”) ... + (“2

*n*choose 2

*n*-1”) + (“2

*n*choose 2

*n*”)

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

*n*choose

*n*” is the largest number in the sum above.

*n*)-th row of Pascal’s Triangle, there are 2

*n*entries in that row. This means that the product of 2

*n*and “2

*n*choose

*n*” must be greater than that sum.

*n*choose 1”) + (“2

*n*choose 2”) + (“2

*n*choose 3”) ... + (“2

*n*choose 2

*n*-1”) + (“2

*n*choose 2

*n*”) < 2

*n*(“2

*n*choose

*n*”)

*, meaning that 4*

^{n}*can be substituted in for that sum.*

^{n}*< 2*

^{n}*n*(“2

*n*choose

*n*”)

*n*gives the inequality that the step was looking for:

*/2*

^{n}*n*< “2

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

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

*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:

8╫ = 7 • 5 • 3 • 2 = 210

16╫ = 13 • 11 • 7 • 5 • 3 • 2 = 30030

*n*╫. The upper bound we will try to set is 4

*. So, this is the inequality that needs to be proven:*

^{n}*n*╫ < 4

^{n}*n*. Then, it can be proven for all even values of

*n*.

*n*is odd, then it can be rewritten as 2

*m*+ 1 assuming that

*m*is an integer (see definition of odd number). Throughout the proof, quantities like “2

*n*choose

*n*” and “2

*m*choose

*m*” have come up, but the row of Pascal’s Triangle it refers to is always an even numbered row (2

*n*and 2

*m*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

*m*+1 choose

*m*” is equal to “2

*m*+1 choose

*m*+1.”

*m*+1 choose

*m*” = “2

*m*+1 choose

*m*+1”

*m*+1 choose

*m*” to both sides of this.

*m*+1 choose

*m*” = “2

*m*+1 choose

*m*+1”

“2

*m*+1 choose

*m*” + “2

*m*+1 choose

*m*” = “2

*m*+1 choose

*m*+1” + “2

*m*+1 choose

*m*”

2(“2

*m*+1 choose

*m*”) = “2

*m*+1 choose

*m*+1” + “2

*m*+1 choose

*m*”

*m*+1)-st row of Pascal’s Triangle. But, what if the sum of all of the elements in the (2

*m*+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.

*m*+1 choose

*m*”) < (“2

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

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

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

*m*+1 choose 2

*m*”) + (“2

*m*+1 choose 2

*m*+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:

*m*+1 choose

*m*”) < 2

^{2m+1}

(“2

*m*+1 choose

*m*”) < 2

^{2m+1}÷ 2

^{1}

(“2

*m*+1 choose

*m*”) < 2

^{2m+1–1}

(“2

*m*+1 choose

*m*”) < 2

^{2m}

(“2

*m*+1 choose

*m*”) < (2

^{2})

^{m}

(“2

*m*+1 choose

*m*”) < 4

^{m}

^{}

*m*+1 choose

*m*.” Recall the formula that was used to find exponents of primes in step 1 and step 2.

*v*

*(“2*

_{p}*n*choose

*n*”) =

*v*

*((2*

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

*v*

*(*

_{p}*n*!)

*m*+1 choose

*m*” fairly easily.

*v*

*(“2*

_{p}*m*+1 choose

*m*”) =

*v*

*((2*

_{p}*m*+ 1)!) - 2

*v*

*(*

_{p}*m*!) -

*v*

*(*

_{p}*m*+ 1)

*m*+1 are difficult to analyze, but what about between

*m*+2 and 2

*m*+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 (2

*m*+1)!. So, it can be guaranteed that each prime between

*m*+2 and 2

*m*+1 is a factor of “2

*m*+1 choose

*m*.” This also means that the product of all primes between

*m*+2 and 2

*m*+1 is less than or equal to “2

*m*+1 choose

*m*.”

*. So, plugging that inequality in on a different interval (say (*

^{n}*m*+1)╫ < 4

^{m}^{+1}), is a legal maneuver. This is called proof by induction.

*m*+1)╫ < 4

^{m}^{+1}

*m*+1)╫. It was just determined what the upper bound of the product of all primes between

*m*+2 and 2

*m*+1 was as well. If we multiply the primorial of

*m*+1 by the product of primes between

*m*+2 and 2

*m*+1, we will just get the primorial of 2

*m*+1. This number will be less than the product of the two right hand sides.

*m*+1)╫ < 4

^{m}^{+1}• “2

*m*+1 choose

*m*”

*m*+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:

*m*+1)╫ < 4

^{m}^{+1}• 4

^{m}

*m*+1)╫ < 4

^{2}

^{m}^{+1}

^{}

*n*back in for 2

*m*+1 gives:

*n*╫ < 4

^{n}*n*are covered. All that needs to be done is to make sure the even values are covered as well.

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

10╫ = 210 = 9╫

22╫ = 9699690 = 21╫

*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)╫

*n*-1 is odd, we can plug that in to get:

*n*-1)╫ < 4

^{n}^{–1}

^{}

*n╫ = (n*-1)╫, so substituting

*n╫*in for

*(n-*1)╫ gives:

*n*╫ < 4

^{n–1}

^{}

^{n}^{–1 }is definitely less than 4

*, so that can be put on the right-hand side to get:*

^{n}*n*╫ < 4

^{n}

^{}

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.

## No comments:

## Post a Comment