Number Theory: Finite Induction

Today, I want to give you some step-wise instruction sets for using (finite) mathematical induction to verify formulas and establish/verify inequalities. I assume you know and understand the Well-Ordering Principle, the First Principle of Finite Induction, and the Second Principle of Finite Induction. These should be covered somewhere in the very beginning of your Number Theory textbook (or perhaps in the Appendix). Throughout this post, all variables are assumed to be integers.

You will find proofs requiring the use of mathematical induction throughout many classes and textbooks. Today, we are going to focus on two types of problems: those that require you to verify/establish a formula and those that asks you to obtain/establish a particular inequality.

HOW TO VERIFY FORMULAS USING THE FIRST PRINCIPLE OF INDUCTION

Step 1 – “basis for induction” – Verify the formula for the least element.

Step 2 – “inductive hypothesis” – Assume the formula is true for some arbitrary element, usually k.

Step 3 – “induction” – Prove the formula is true for the next consecutive element, that is, k + 1.

Let’s try a few examples.

The first two steps are simple. In the first, you want to verify that the formula works for the least element. You will be given a range for which the formula works—here, it is integers greater than or equal to one. So, 1 is our least element. We verify the formula is accurate for n = 1. In step 2, you state your hypothesis, that is, the assumption that the formula is true for some arbitrary n value. I like to use n = k for my arbitrary value, but you can use any variable you’d like. We let this k be greater than 1 because we already verified the formula works for n = 1. Step 3 is where students have the most trouble.

In this step, you have to actually prove that the formula is true for the next consecutive element, which is k + 1. It is very helpful to write out what you hope to accomplish, which I usually precede by writing “want to show.” Start with the left side of the formula and group the terms together that appeared in Step 2. We already know that these first k terms “work” in the formula. After this, it is only a matter of manipulation.

Combining the fractions is the next logical step (be sure to get a common denominator first); then just see where simplifying will take you. Eventually, you get to a point where you can’t simplify anymore, and that usually means it’s time to factor. How do you know which factors to check for? Look back at your stated goal—you see that (k + 1) appears in the numerator. I simply divided (long division of polynomials) the numerator by (k + 1) and then rewrote the second factor to better resemble the formula.

You should end with a statement that summarizes the induction process. That is, since the formula works for n = 1 and works for k + 1, we know the formula works for all integers greater than or equal to 1. Many professors will dock points if you do not summarize your proof with a concluding statement, so don’t forget to do that!

All problems like this work similarly. More difficult problems will simply require more manipulation in the third step. The first two steps are always about the same—the only difference may be the number that requires verification in the first step. Remember that you always want to verify the least element. It is usually 1, but not always, so pay attention to that.

Here is another one worked out, but with some of the steps consolidated.

Again, Steps 1 and 2 are pretty much the same.

Just as before, we group the first k terms that appeared in Step 2 and use the formula for them. The rest is pretty straight-forward, I think. In the “factoring” step, I factored (k + 1) from the numerator first, then factored (2k + 1) from what was left. How did I know to factor those out? I considered my stated goal and saw that these factors appeared there. If you try to factor something that appears in your goal and do not get the answer you need, then you should check your work—you probably made a mistake earlier (or in your factoring work).

HOW TO VERIFY FORMULAS USING THE SECOND PRINCIPLE OF INDUCTION

The Second Principle is very similar to the First.

Step 1: Verify the formula for all necessary least elements.

Step 2: Assume the formula is true for all elements less than some arbitrary element, k.

Step 3: Prove the formula is true for the arbitrary element k.

Here is an example.

Notice that the nth number is defined in terms of the previous two. So the 3rd number is defined in terms of numbers a1 and a2; the fourth in terms of a2 and a3; etc. This is why n is limited by 3. If n = 2, there is no number defined for a(n-2) = a0. This changes our first step—we must verify the formula for the least necessary elements. In this case, we verify the first two elements. In other cases, you may have to verify the least 3 or 4 elements. It all depends on how the nth number is defined.

Step 2 also shows us a difference between the two Principles. Notice that I am assuming the formula is true for all integers between our least element (1) and k, not including k. We must assume this because if we only assume it works for k, we don’t know if the formula is true for a(k-1) or a(k-2), but we must use those in order to make our proof! After making the assumption, note the numbers that you will need in the proof, which all depends on how that nth number is defined. In this case, I need a(k-1) and a(k-2).

Begin by defining what you want to show, which is simply the formula with n = k. Use the definition given in the problem to start with, then replace a(k-1) and a(k-2) by the formula definitions from Step 2 (underlined in blue). Now, simply manipulate the numbers until you reach your goal. In this instance, I multiplied through the parentheses, then simplified (green and red underlines). Notice how I simplified the red portion: the rules of exponents will come up over and over again in Number Theory! After simplifying, I can factor the power of 2 from the first two terms (leave the last term alone). After that, I end up with 10, which is 5 * 2, and this 2 can simplify with the power of 2 I already have. And I am left with what I wanted to determine.

As before, you should end your problem with a conclusion of some sort. The Second Principle is essentially the same as the First. Since the formula is true for all values up to and including an arbitrary value k, we can say the formula is true for all numbers on which it is defined, which is n >= 1 in this case.

HOW TO USE INDUCTION TO ESTABLISH AN INEQUALITY

Step 1: Verify the inequality for any necessary least elements.

Step 2: Assume the inequality is true for some arbitrary element (obtain equation A).

Step 3: Note the inequality desired for the next consecutive element (obtain equation B).

Step 4: Manipulate Eq. A so that the left side of Eq. A matches the left side of Eq. B (obtain equation C).

Step 5: Connect Eq. B and Eq. C by an inequality (obtain equation D).

Step 6: Prove Eq. D is true and extrapolate to form statements that prove Eq. B.

I know, this sounds very complicated. It will make more sense as we go through an example!

These problems are long and can get a little confusing, which is why I label pertinent equations (A, B, C, etc). I encourage you to do this as well as you work.

In Step 1, we verify that the inequality is true for the least element, n = 1. It is true. In Step 2, we assume the inequality is true for an arbitrary value k, which is greater than 1 (we already verified 1) and form our first equation, Eq. A, by inserting k for n into the inequality. Simple so far. In Step 3, we determine what we want to prove. We want to show that the inequality works for the next consecutive element, that is, k + 1. To obtain Eq. B, we simply insert (k+1) in place of n in the original inequality.

Here is where everything is complicated a bit. The purpose of the next few steps is to obtain a new inequality that will allow us to prove Eq. B. You are probably familiar with the Squeeze Theorem which works on a similar principle—if a < b and b < c, then we can definitively say that a < c. Think of Eq. B as our “a < c.” We now need two inequalities that link together that will allow us to conclude that Eq. B is true.

In Step 4 (above), we are going to form Eq. C that will be our “a < b” statement. Begin with Eq. A and manipulate it until the left side of Eq. A matches the left side of Eq. B. In order to do this, you need the items found in the blue box. You need to be very familiar with exponential rules and factorials in order to do these problems. After simplifying, we have obtained Eq. C. The left side matches the left side of Eq. B. Remember that whatever you do to one side of an equation, you must do the same to the other—the right side of Eq. C no longer matches Eq. A and in fact, doesn’t match any of our equations.

Step 5 is where we form our “a < b < c” statement in order to figure out our “b < c” statement. I like to think of opening up Eq. B; prying it apart in the middle and leaving a big gaping hole. Notice that we have the “a” and “c” portions of our “a < b < c” statement in place now. Equation C fits in this hole (green). It “links” up with the left side because of Eq. C.  The portion underlined in red (“b < c”) is the portion that is “missing”… we have not previously established it. This portion is labeled Eq. D.

Step 6 is the proof of Eq. D. Begin by simplifying the right side. Again, you need to be familiar with factorials here—rewrite the right side. The easiest way to prove an inequality is to move all relevant terms to one side (so that 0 is on the other) and then prove that the terms sum/produce a positive or negative number (depending on the sign). Here, I chose to subtract the right side from the left, but you could subtract the left side from the right. Now all we need to do is simplify and prove that the left side is negative (or is equal to 0).

Always be on the lookout for common factors. If I hadn’t rewritten the factorial on the right side, I would not have any common factors. So, factor out anything that is in common and simplify what remains.  Again, be on the lookout for common factors—I found another at the bottom of this photo—and factor them.

Now we need to show that this inequality is true—that the left side really is negative. Consider the limitations in place at the beginning of the problem—we let k > 1. From here, we can multiply both sides by -2, which reverses the inequality; so -2k < -2, which means -2k is negative (obvious, yes?). If k > 1, then 2k > 2. Three (3) is the least possible value that 2k could be equal to; if 2k = 3, then (2k)! = 3! = 6; therefore, (2k)! >= 6. I simplified this by saying (2k)! is at least 2. Either way, we know it is positive. And again, since k > 1, k+1 is definitely greater than 2 and is therefore positive as well.

So, we have a negative multiplied by two positives. This will always yield a negative result and so, we know that our final statement is true. Therefore, Eq. D is true (as that’s where we began in Step 6). Since Eq. D is true, our linkage of inequalities (“a < b < c”) is also true. Since this is true, we can say that the left side is less than or equal to the right side and therefore the inequality from Step 3 (Eq. B) is true, which is what we wanted to show.

We essentially began with “a < b” (Eq. C). We found a “c” such that “b < c” (Eq. D) and proved it. Therefore, we could safely say that “a < b < c” and thus, “a < c” (Eq. B).

I know this is confusing, but it will get easier with practice. Just keep working at it. Labeling the equations is a huge help, too.

I hope you now feel more comfortable with mathematical (finite) induction. It is a method of proof you will come across throughout even a short mathematical career/study track.