What is Mathematical Induction?

Last week’s exploration of a problem involving the Fibonacci sequence, has led me to delve into that and related concepts. In order to say much about the Fibonacci numbers, we have to first explore the concept of proof by mathematical induction. We’ll introduce it here, and then dig deeper next time.

Knocking down all the dominoes

We’ll start with this basic question from 1998:

Explaining Mathematical Induction

I have to do a report and the math article involves mathematical induction. I have not yet learned this and wanted to know what mathematical induction is.

Doctor Barrus answered:

Hi, Kate.

Mathematical induction is one way mathematicians prove things. What it is, basically, is this:

Let's say I wanted to prove something about numbers [positive integers].

Step 1: First I would show that this statement is true for the number 1.

Step 2: Next, I would show that if the statement is true for one number, then it's true for the next number.

This is often described as three steps: (1) proving the base case, (2) stating the inductive hypothesis, and (3) the inductive step, proving the next case from that assumption.

These two steps complete a proof. It's kind of like dominoes. If you want to knock down all the dominoes you have, they all have to be lined up in the right way (so that they'll knock each other over), and you have to be able to knock the first domino down (so that all the others will fall). 

Well, showing that your statement is true for 1 is like making sure you can knock down the first domino. Proving that if your statement is true for one number, then it's true for the next, is like making sure all the dominoes are lined up correctly, meaning that when one falls down, it will knock down the next one. When you put these things together - everything's lined up and you can knock down the first one - you've proved that you can knock down all the dominoes, or that your statement is true for all positive whole numbers.

I hope that's understandable. But basically, mathematical induction is just a way of proving things about numbers.

So, we have an infinite set of claimed facts all lined up so that each one implies the next one is true. If we start the process by proving the first one is true, then all of them must be true, because each implies the next.

Demonstrating the three steps

It’s easier to understand the idea with an example. Let’s look at a very simple one from 1997:

Proof by Induction

Prove by induction on n that |A^n|=|A|^n.

I'm not sure how to do this problem at all.

Doctor Sydney answered:

I'm glad you wrote. Induction can be confusing at first, but once you get the hang of it, it will be okay. 

You will probably remember how to do proofs by induction if you have a good understanding of how the proofs work. Let's quickly review this. 

Proofs by induction are commonly used when you want to prove a statement that depends on some variable (usually named n) for all positive integer values of that variable. For instance, in your problem you want to prove the above equality for all positive integer values of n. In other words, you want to show that the above equality holds for n = 1, n = 2, n = 3, and so on.

Induction is not applicable when the variable is a real number. But it’s possible for n to start at 0 or any other particular integer.

How does the inductive proof do this?

First, it demonstrates that the statement holds for the "base case" - usually the n = 1 case.

Next, when doing an inductive proof, you assume that the statement holds for the kth case. What is the kth case, you may be wondering? It is any case. We write k because we want k to be able to represent any positive integer. 

Next, you prove that the (k+1)st case holds assuming that the kth case holds. Then the proof is done! Why? Well, think about it. In the first part we showed that the statement we are trying to prove holds for n = 1, right? Then, in the second part of the proof, we demonstrate that if the kth case holds, so does the (k+1)st case. Combining these two pieces of information, we see that since the 1st case holds (as proven in the first part of the proof), the 2nd case must hold too (according to the second part of the proof); well, if the 2nd case holds (as just demonstrated), so too must the third case hold, right? And so on. Thus we have shown that the statement holds for any n.

You’ll note that Doctor Sydney has the three steps I mentioned, and also that the inductive hypothesis step (stating that the kth case is true) is not merely a restatement of the problem, because the problem to be proved is that a statement about n is true for all n, while this is about any specific number k.

A simple example

This will all become much more clear if we do an example. Let's look at your example. To show that |A|^n = |A^n| for all n by induction, we follow the steps outlined above.  

1. Show that the statement holds for the base case n = 1.  

When n = 1, the equation is |A|^1 = |A^1|, right? Does this equation hold? Yes, because anything to the first power is itself, so |A|^1 = |A| and |A^1| = |A|. Hence, |A|^1 = |A^1|. Thus, we have shown that the equality holds for n = 1.

It wasn’t explicitly stated what “all n” means; we could take it to mean any non-negative integer n, in which case the base case is n = 0. That, too, is easily proved: \(|A|^0 = 1\) and \(|A^0| = 1\)

2. Now, we assume that the equality holds for the kth case. That is, we assume that |A|^k = |A^k|.

3. We now want to prove that the (k+1)st case holds.  

We want to prove that |A|^(k+1) = |A^(k+1)| (**). Let's use what we know. In inductive proofs, proving that the (k+1)st case holds almost always relies on the fact that we have assumed that the kth case holds. So, let's rewrite the equation for the (k+1)st case in a way that will allow us to use information from the kth case.  

We know that |A|^(k+1) = |A|^k * |A|, right? Similarly, we have that |A^(k+1)| = |A^k * A| = |A^k| * |A|.

Substituting into (**), we see that we want to prove that:

  |A|^k * |A| = |A^k| * |A|

I bet you can prove that the equation above holds. I'll leave the last steps to you.

Once you have proved that the above equation holds, you will have proven that the (k+1)st case holds, and thus, the proof will be over.

The proof is, of course, simple: Since we have assumed for this step that \(|A|^k = |A^k|\), we can just replace \(|A|^k\) with \(|A^k|\).

Again, the reason the proof works is as follows: First, we prove that the equation holds for n = 1. Next, we prove that if it holds for the kth case then it must also hold for the (k+1)st case. Since the equation holds for n = 1, it must also hold for n = 2 (the second part of the proof shows that if the kth case holds then so must the (k+1)st. Here, k = 1). But if the equation holds for n = 2, it must also hold for n = 3, and so on. Does that make sense to you?

The proof has set up these dominoes, and given the first one a push:

This proof, of course, was just for practice; we don’t need induction to prove such an obvious fact. But most such proofs are considerably more interesting, as we’ll see next week.

Assuming what we want to prove?

A good way to understand a concept better is to try to defend it against attack. Here is a question from 1998, presumably reflecting a statement the student was assigned to respond to:

Mathematical Induction

"Proof by induction does not prove anything, because in the inductive step, one makes the assumption that P(k) is true. Since one has to do this for each k, one has assumed what was to be proved in the first place, and so the proof is invalid."

What is wrong with the above argument?

In a proof, you can’t just assume that you are right. So why is it okay to assume the kth case is true?

Doctor Allan answered:

Here is what goes wrong in the argument:

When you generally prove something using induction, you first prove that the theorem is true for (typically) n = 1. This is called the basis of the proof. Afterwards you prove that if it is true for P(k) then it is true for P(k+1).

As the argument states, it is true that you assume P(k) in order to prove P(k+1), but you can do that because you have proven the statement for P(1). So the argument forgets the basis of the proof: that you prove P(1) to start with.

We can’t just assume that any one case is true; but we are not doing that. We are proving one case, and then proving the other cases follow from it.

Let me give you an example:

Say I want to prove that n = n+1 for all n, and I assume P(k) as in the argument. Then k = k+1. I need to prove that k+1 = k+2 (the statement P(k+1)). But k+1 = k + 1 = k+1 + 1 = k+2 (here the second equality comes from the fact that we have assumed P(k). This is nonsense, and it only works because I have forgotten to prove the basis: that 1 = 1+1 = 2, and of course I cannot do that.

In this example, we have proved the last (inductive) step, but never proved a base case, so the inductive step has no ground to stand on. It may be true that B follows from A, but if A is not true, then we have accomplished nothing. But if A is true, then we will know that B is true.

So as you see it is quite easy to prove weird things using induction if you forget the basis of the proof, and that is exactly the case with the argument you mention. If you prove P(1) and thereafter prove 'if P(k) then P(k+1)' then proof by induction is a completely sound method of proof.

There are several classic fallacious “proofs” using induction. One, which is referred to in the Ask Dr. Math FAQ page on False Proofs, claims to prove that all people in Canada are the same age. This one is subtle, because rather than being due to failure of the base case, it comes from the chain being broken elsewhere.

Proving what we already know, or assuming what we don’t?

Here is a long question from 2012 making a stronger argument against induction, which I’ll take in pieces:

Inductive Misunderstanding

I have a question about mathematical induction.

I'm sure my reasoning is out of line somewhere, but I can't seem to get past thinking that it is not useful in the sense of being a proof. Would you be so kind as to show me the hole in my thinking? :)

I have had mathematical induction explained to me two separate ways (one of which must be erroneous).

Given A1, Ar, and Ar+1:

a.) One must ASSUME that Ar holds true. If Ar is true, and the base case -- A1 -- is also true, and we illustrate that if Ar holds true for Ar+1, we may assume that Ar is proven true and that it holds true for all integers.

b.) One must KNOW that Ar holds true. If Ar is true, and the base case -- A1 -- is also true, and we illustrate that Ar holds true for Ar+1, we may assume that Ar is proven true and that it holds true for all integers.

Neither of these is worded very well. In his notation, \(A_r\) is the general proposition to be proved for any value of variable r; \(A_1\) is the base case, where the variable r is 1, \(A_{r+1}\) is the next case. The statement “\(A_r\) holds true for \(A_{r+1}\)” suggests that Brandon is a little confused about the notation. Subsequently he will use “n” and “a” in place of r without explanation. So a major goal will be to clarify what the symbols mean.

It might help to look at an example. Let's suppose we have the example of an arithmetic series. Let us follow method b.

           Ar = n(n + 1)/2 

Proving for 1 (base case):

   1(1 + 1)/2 = 1

       Ar+1 = (a + 1)(a + 2)/2

(I cheated, but if you do the math, it works).

Using method b, we have, at least to my understanding, proven Ar to be true. However, it was known that Ar was true beforehand, so what is the sense in proving it again? That suggests that mathematical induction (at least in the form of method b) is useless. It proves only what has already been proven to be true!

What Brandon means, I believe, is that we are trying to prove that for any positive integer n, the sum \(1 + 2 + 3 + … + n = \frac{n(n+1)}{2}\), so the rth case would claim that \(1 + 2 + 3 + … + r = \frac{r(r+1)}{2}\), and the r+1st case would claim that \(1 + 2 + 3 + … + r + (r+1) = \frac{(r+1)(r+2)}{2}\).

Brandon is using \(A_r\) to represent both a statement that can be true, and an expression that has a numerical value. He is also failing to distinguish between all n and a specific r. These confusions are probably both common among students!

His issue is that if we know already that \(A_r\) is true, then there is nothing to prove. His other idea is that we merely assume that \(A_r\) is true, which is no better:

Conversely, if one thinks about method a, it is equally as useless.

Given method a, let's suppose the following:

Ar = 1 such that Ar is any integer, including an integer larger than 1, such as 2. Remember, we're assuming Ar to be true, so we can theoretically do this.

            1 = 1 (base case)
       Ar + 1 = 1 + 1

Recall that Ar = 2, and therefore, Ar+1 also is equal to one. That insinuates that we can assume anything at all to be true, and we can prove it, regardless of whether or not it is in alignment with reality.

That leaves us only with method b as the valid use of mathematical induction, and we mentioned before that it is useless.

I just can't seem to see wrap my mind around how mathematical induction could be useful, nor do I see the error in my thinking.

Building an infinite staircase

Doctor Rick answered, first clarifying the notation, carefully describing what induction means:

Hi, Brandon,

Both descriptions of mathematical induction you present are flawed. Many students miss the same critical elements of the method that are missing in your descriptions.

Let's say we want to prove that a certain proposition is true for all integer values of n greater than zero. I'll call the proposition P(n): it says that something is true for a *particular* value of n.

We must first prove that the proposition to be proved is true for the least value of n, which is 1 in my example (as is commonly the case). That is, we prove that P(1) is true. That's the "base case."

Now, we assume that P(n) is true -- for some *particular* value of n. On this assumption, we prove that a *different* proposition is true -- namely, P(n + 1). We aren't assuming what we want to prove; we're proving that one proposition, P(n + 1), follows from the truth of another, P(n).

What we have is a sequence of propositions, and our goal is to prove that they are all true. Since each is a separate proposition, we may assume one of them true in proving the next.

This second part of the proof provides sort of a template for an infinite set of proofs, an infinite line of reasoning, as follows:

First, we have proved that P(1) is true.

Then, using the template, we can prove that, given that P(1) is true (and we know it is), therefore P(2) must be true. The logic holds, so now we know that P(2) is true.

Next, again using the template, we can prove that, given that P(2) is true (and we know it is), therefore P(3) must be true. Thus P(3) has been established as true.

The path has been laid for proving in the same way that P(4) is true, and P(5) is true, and so on, up to any finite integer k for which you wish to prove P(k). Knowing HOW to prove that P(k) is true, we don't have to do it all the way out to P(1000000) or whatever; we know it's true.

You might think of our proof as writing a computer program that will carry out the 1,000,000 little proofs needed to get to P(1,000,000). Once we write the program, we know it can, in principle, keep proving as far as we choose.

We aren't assuming what we want to prove, or proving what we already know; you're right, the first would be a logical fallacy, and the second would be unnecessary. Rather, we're proving that IF one thing is true, THEN the NEXT thing must be true. We set one step of an infinite staircase in place, and provide a blueprint showing how to build any step while standing on the step below it. Following the blueprint repeatedly, we can build the infinite staircase one step at a time. That's what mathematical induction is.

Does that make sense?

We might think of the base case as the floor, which we establish on its own; then each step is supported by the step below it. The blueprint here corresponds to the program I suggested earlier. Here is a new image for an inductive proof:

Brandon replied:

Thanks so much for the response! That was certainly not something I could have chewed through by myself!

You have saved me a great deal of grief. I'm very bad at abandoning problems when I don't have any leads, and this one ended up being a little time sucker.

Next week, we’ll look at some deeper examples of inductive proof.