Math Awareness Month Part 1: Magic Squares

I explained a bit in my last post that April is Math Awareness Month, as well as linked to the poster on www.mathaware.org. In honor of this occasion, I plan to make my posts this month relevant to the pages on the website and the mathematicians hosting them.

April 1st was a day on magic squares, and I am honored to have been the host of that page. There is a recent performance of me doing it, tutorials on how to make various magic squares, and different activities and questions that can further your magic square experience. Click here to see the page.

Rediscovering Trigonometry Part 4: More Useful Formulas

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


Now that we have discovered some useful trigonometric identities, we can continue to build on them and create many more. There are an infinite number of trigonometric identities out there (not all of them have been created of course), but we will stick to two in this post: the product-to-sum formulas and the sum-to-product formulas.

Take the four angle addition/subtraction formulas we discovered in our first week. I will use A and B as our letters rather than alpha and beta.

1. sin(A + B) = sinAcosB + cosAsinB
2. sin(A – B) = sinAcosB – cosAsinB
3. cos(A + B) = cosAcosB – sinAsinB
4. cos(A – B) = cosAcosB + sinAsinB

These can be messed with very easily to create some new formulas. For instance, adding together the first two formulas gives:

sin(A + B) + sin(A – B) = sinAcosB + cosAsinB + sinAcosB – cosAsinB
2sinAcosB = sin(A + B) + sin(A – B)
sinAcosB = [sin(A + B) + sin(A – B)]/2

We now have a new identity. This can be now be used to solve a whole new range of problems and generate a whole new range of identities. The same steps can be done by subtracting the second equation from the first, adding the third and fourth together, and subtracting the fourth from the third. This creates the four product-to-sum identities.

These four formulas can be rewritten in a way that converts the sum into a product. Let's rewrite the variables as the following:

a + b = A
a – b = B

Making this change, we can then perform some operations to get a whole new set of formulas. These are called the sum-to-product identities.

These can then be built upon to generate whole new sets of formulas as well. Though the actual mathematics here might be a bit complicated, the idea is simple. Mathematics is always continuing to be developed, and this can be done through building upon previous ideas to form new ideas that help solve new problems. Trigonometry is a great place to see this sort of thing happen.

Rediscovering Trigonometry Part 3: Half Angle Formulas

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


Last week, we figured out a way to figure out trigonometric functions for twice a given angle. This week, we will do the same, but for determining the trigonometric functions for half a given angle. First, let's discuss what half of an angle means.

Remember that there are 360° in a circle, or 360° in a full revolution. This means that a number like 370° can also be expressed as 10°. Though they are different measurements, plugging 370° into a trigonometric function will yield the same answer as 10°. It is also equivalent in most other situations in mathematics.

For double angle formulas, we did not need to discuss this. This is because when doing double angle formula calculations with these measurements, there would be no issue.

sin(2 • 10°) = sin(20°)
sin(2 • 370°) = sin(740°) = sin(740° - 720°) = sin(20°)

Note that 720° is two full revolutions around a circle, and thus, it can be subtracted off when performing a trigonometric operation.

But performing a half angle calculation will create more of an issue. Let's use 10° and 370° again.

sin(1/2 • 10°) = sin(5°)
sin(1/2 • 370°) = sin(185°)

These answers are not the same. Since they are both in the 0° - 360° interval, we cannot make any assumptions. We do know that the sine and cosine of 185° are the negative sine and negative cosine of 5° respectively, but this proves that they are not equal. If one were go up to 730°, they would be back to normal, however.

sin(1/2 • 730°) = sin(365°) = sin(365° - 360°) = sin(5°)

This means that for every angle, the half sine and half cosine function should yield two answers. The two answers should have the same absolute value, but different signs (they are the same number, but one is negative and one is positive). You may already have a function in your head that can create this type of situation, but we will be able to derive it as well.

Take a variation of the cosine double angle formula that we derived last week:

cos(2α) = 1 – 2sin²α

Let's try to isolate sinα. We would first add that to the left hand side and subtract the cosine of 2α over to the right hand side.

2sin²α = 1 – cos(2α)

Divide through by 2 to get:

sin²α = (1 – cos(2α))/2

And square root both sides to get:

sinα = ±√((1 - cos(2α))/2)

Notice how there is a ± sign in front of the square root. This is because when one squares a positive or negative value, it becomes positive. For instance, the equation x² = 25 would be solved as x = ±5 because (5)(5) = 25 and (–5)(–5) = 25. The same thing happened here. But also remember what we found before. We proved through logic that the half sine and half cosine of an angle has two answers, one negative and one positive. With that in mind, we can see that this is the accurate way to write the square root (some derivations call for just a positive answer such as the Distance Formula).

Let's replace angle α with α/2 to keep the half angle definition. This gives a formula of:

sin(α/2) = ±√((1 - cosα)/2)

Let's derive a cosine half angle formula. We can take another variation on the cosine double angle formula and go forward.

cos(2α) = 2cos²α – 1

This time, we will only need to add one to both sides to isolate the cosα term. Let's also flip the equation around to make it simpler.

2cos²α = 1 + cos(2α)

Divide through by 2 to get:

cos²α = (1 + cos(2α))/2

And square rooting both sides yields:

cosα = ±√((1 + cos(2α))/2)

Again, we end up with a ± sign in the formula. This means that we probably did everything correctly, as logic shows we will need this sort of sign to create two answers. Rewriting α as α/2 gives a final formula of:

cos(α/2) = ±√((1 + cosα)/2)

It is tough to see what these formulas actually look like in this formatting, so I have written them out in LaTeX so you can see what is going on more conveniently.

These formulas themselves are pretty cool, but the logic involved in finding them is also very interesting. The fact that we could predict the nature of the function before we even found it is really helpful. This can be huge in trying to figure out the right way to go about solving a problem.

Rediscovering Trigonometry Part 2: Double Angle Formulas

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


Last week, we developed some formulas that could calculate the sine, cosine, and tangent of the sum and difference of two angles. This proves useful when trying to calculate the exact sines/cosines/tangents of angles that are not in special right triangles (45-45-90, 30-60-90, 18-72-90).

What if we wanted to find the exact values for double a certain angle. Let's say we know the following:

sin18 = (√(5) - 1)/4
cos18 = (√(10 + 2√(5)))/4

How could we calculate the sine of 36°? We know the sine angle addition formula from last week, but it would be much easier to have a generalized version of this. Let's take a look at it.

sin(α + β) = sinα cosβ + cosα sinβ

What if we were finding the sine of 2α? Let's see what the formula would tell us:

sin(2α) = sin(α + α) = sinα cosα + cosα sinα = 2sinα cosα

So with some pretty simple computations, we get the formula:

sin(2α) = 2sinα cosα

That's a pretty simple formula. To find the sine of 36°, we could just do some easy manipulation with the values from up top.

sin36 = sin(2 • 18) = 2 • ((√(5) - 1)/4) • ((√(10 + 2√(5)))/4) = (√(10 - 2√(5)))/4

This sort of computation is clearly very useful when you are studying trigonometry. It wouldn't be practical in the sense that we use it in our day-to-day lives, but I think it is clear how useful this is to mathematicians and astronomers. I also find it really cool that these seemingly random irrational values can be derived exactly using just some basic mathematics.

Let's create a cosine formula. We know from last week that:

cos(α + β) = cosα cosβ – sinα sinβ

Substituting α in for β gives:

cos(2α) = cos(α + α) = cosα cosα – sinα sinα = cos²α – sin²α

This is the formula that naturally comes out:

cos(2α) = cos²α – sin²α

Knowing that sin²α + cos²α = 1, this can be rewritten in a few different ways:

cos(2α) = cos²α – sin²α
cos(2α) = 2cos²α – 1
cos(2α) = 1 – 2sin²α

This is extremely convenient, as the problem can be made much easier depending on what information you have. If you only know the sine of the angle, the third formula will work. If you only know the cosine, the second formula will work. There are also times where the first formula might be most convenient.

As you can see, it is pretty simple to do the work to come up with the double angle formulas, probably even easier than applying them in many cases. I encourage you to do the same process as we have done for sines and cosines to generate one for tangents, using the tangent formula we found last week. You will get a very pretty result.

Also, it can be fun to play around with these and find the exact sines and cosines of various angles. You will also see that there are many ways to write these different values. This is because they are irrational numbers. You could find the sine of 105° by doing sin(45 + 60), sin(90 + 15), sin(180 - 75), or many other variations. These could very well give different looking answers, but if the math was correct, the actual results will be equal.

Rediscovering Trigonometry Part 1: Addition and Subtraction Formulas

In January, I did a series with some heavier mathematics, involving lots of number theory, combinatorics, and some fairly difficult manipulation. Last month, we took a little rest from this by talking a bit about casino games and optimal strategies. The mathematics we used was more probability and game theory. This month, I thought we could explore something completely different that is also extremely interesting. It is taught in school (much of the material in this post actually comes straight from my math class), but maybe not in a fun, thought-provoking way. This month, we will dive into trigonometry.

If you want to brush up on your basic foundational trigonometry, please click here. It is my post on the Law of Cosines, but also explains at the beginning what the sine, cosine, and tangent functions are. I will make sure to prove any other trigonometric identities we use in this series (or link to a proof), so all you need to know is what a sine, cosine, and tangent is.

Now we are ready to derive our first identity. We will try to figure out a simpler way of writing sin(α+β). There are many proofs of this, but I am using one that I found at www.themathpage.com. Let's start with a diagram to help explain this idea.

Create the line AB.

Rotate it to point C, creating the angle α.

Rotate it to point D, creating the angle β.

Draw DE perpendicular to AB.

Draw DF perpendicular to AC.

Draw FG perpendicular to AB.

Draw FH perpendicular to ED.

We are trying to figure out the sine of α+β, which can be written as (ED/DA). First, let's determine the value of the angle HDF (which has already been written in for us).

Note that the lines HF and AG are parallel, with a transversal (a line that intersects both lines) of AF. In geometry, there is a theorem called the Alternate Interior Angle Theorem, that essentially tells us that in this circumstance, the measure of angle GAF is equal to the measure of angle AFH. In other words, angle AFH has a measure of α. Noting that angle AFD has a measure of 90 and AFH has a measure of α, that means angle HFD would have a measure of 90–α. Since a triangle has 180 degrees, having two angle measures in a triangle is enough to get the third. Triangle HFD has an angle of 90, an angle of 90–α, and one more angle that creates a sum of 180 degrees. Do the math and you will find that the angle must be α, and thus, angle HDF has a measure of α as depicted in the diagram.

Now we can try to find the formula. Let's start with the following equality:

ED = GF + HD

Note that we are trying to find what (ED/DA) equals. Because of this, let's divide both sides by DA.

(ED/DA) = (GF/DA) + (HD/DA)

Let's complicate some terms on the right hand side. Multiply the fraction on the left by (AF/AF) and the one on the right by (FD/FD)

(ED/DA) = (GF/AF)(AF/DA) + (HD/FD)(FD/DA)

(ED/DA) is simply the sine of α+β. Looking back at the diagram, (GF/AF) would be the sine of α. (AF/DA) would be the cosine of β. (HD/FD) would be the cosine of α. (FD/DA) would be the sine of β. This gives us the following formula:

sin(α + β) = sinα cosβ + cosα sinβ

This is a beautiful result. The sine of the sum of two quantities can just be pulled apart so easily. This is really cool on its own, and furthermore, it ends up being the foundation of tons more identities. Let's say we wanted to find the sine of α–β. We could just plug (-β) in for β and see what we get.

sin(α – β) = sinα cos(-β) + cosα sin(-β)

These negative terms can be analyzed in a number of ways, but the easiest way to do it is to look at the graphs of the sine and cosine functions.

Graph of y = sin(x)

Graph of y = cos(x)

Notice how the sine graph is symmetric over the origin. Any sin(x) will equal -sin(-x) and any sin(-x) will equal -sin(x). On the other hand, the cosine graph is symmetric over the y-axis. Any cos(x) will equal cos(-x) and -cos(x) will equal -cos(-x). This enables us to simplify the formula much more.

sin(α – β) = sinα cos(-β) + cosα sin(-β)

sin(α – β) = sinα cosβ + cosα (-sinβ)

sin(α – β) = sinα cosβ – cosα sinβ

Fantastic. What if we wanted to find the cosine of the sum of two angles? Going back to our original diagram, we can start with the following expression:

EA = GA - FH

Dividing through by AD creates the desired left hand side.

(EA/AD) = (GA/AD) - (FH/AD)

Multiply the term on the left of the right hand side by (AF/AF) and the right term by (DF/DF) to get:

(EA/AD) = (GA/AF)(AF/AD) - (FH/DF)(DF/AD)

And turning this into the appropriate functions gives:

cos(α + β) = cosα cosβ – sinα sinβ

Doing the same thing as before gives a subtraction formula of:

cos(α – β) = cosα cosβ + sinα sinβ

Finally, let's try to create a tangent formula. Knowing that dividing the sine by the cosine will give the tangent, let's try dividing the two formulas by each other.

sinα cosβ + cosα sinβ

cosα cosβ – sinα sinβ

Divide each term through by cos cosβ.

(sinα cosβ)/(cosα cosβ) + (cosα sinβ)/(cosα cosβ)

(cosα cosβ)/(cosα cosβ) – (sinα sinβ)/(cosα cosβ)

Many terms will now cancel.

(sinα)/(cosα) + (sinβ)/(cosβ)

1 – ((sinα)/(cosα))((sinβ)/(cosβ))

Turning the sine and cosine ratios into tangents gives a formula of:

tanα + tanβ

1 – tanα tanβ

And there's the formula! If you wanted to create a subtraction formula, you would just note that the tangent function is symmetric over the origin (or it is an odd function), and plug in the necessary values to get:

tanα – tanβ

1 + tanα tanβ

I think that these are really cool formulas. But they are also very practical. For instance, let's say you want to find the exact sine of 75°. We know that sin(45) = (√2)/2, sin(30) = 1/2, cos(45) = (√2)/2, and cos(30) = (√3)/2. So, this can be determined with the sine angle addition formula.

sin(75) = sin(30 + 45) = sin30cos45 + cos30sin45 = (1/2)((√2)/2) + ((√3)/2)((√2)/2) = (√(2) + √(6))/4

Knowing that the Greeks did some manipulation with the regular pentagon to find an exact sine of 72°, we can plug all of this information into the sine angle subtraction formula to find the exact sine of 3°. We can then eventually make our way down to 1°, which gives us the ability to generate the sines of all of the angles on the trig tables that mathematicians now use today.

Next week, we will use these formulas to create more generalizations that will make many of these trig table computations much much simpler. And give us some really pretty formulas in the process.

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.