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 knowwhat 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 istrue for the number 1. Step 2: Next, I would show thatifthe 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 wantto knock down all the dominoesyou have, they all have to be lined up in the right way (so that they'llknock each other over), and you have to be able toknock the first domino down(so that all the others will fall). Well, showing that your statement istrue for 1is like making sure you can knock down the first domino. Proving that if your statement istrue 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) forall positive integer valuesof 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 forn = 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, youassume that the statement holds for the kth case. What is the kth case, you may be wondering? It isanycase. We write k because we want k to be able to represent any positive integer.Next, youprove 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 forany n.

You’ll note that Doctor Sydney has the three steps I mentioned, and also that the inductive hypothesis step (stating that the *k*th 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 nby induction, we follow the steps outlined above. 1. Show that the statement holds for thebase casen = 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, weassumethat the equality holds for the kth case. That is, we assume that|A|^k = |A^k|. 3. We now want toprovethat 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'srewrite the equation for the (k+1)st casein 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 provedin 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 *k*th case is true?

Doctor Allan answered:

Here is what goes wrong in the argument: When you generally prove something using induction, you firstprovethat the theorem is true for (typically) n = 1. This is called the basis of the proof. Afterwards you prove thatifit is true for P(k)thenit 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), butyou can do that because you have proventhe 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 becauseI 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 seeit is quite easy to prove weird things using inductionif 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 inductionexplained to me two separate ways(one of which must be erroneous). Given A1, Ar, and Ar+1: a.) One mustASSUME 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 mustKNOW 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). Usingmethod 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) isuseless. 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 *r*th 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 aboutmethod 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 thatwe 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 methodthat 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 truefor 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, weprove that P(1) is true. That's the "base case." Now, weassume 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'reproving 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 ofa 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'tassuming what we want to prove, orproving 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 showinghow 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.

Pingback: Inductive Proofs: Four Examples – The Math Doctors