Importance of the base case in a proof by induction

In Precalculus, Discrete Mathematics or Real Analysis, an arithmetic series is often used as a student’s first example of a proof by mathematical induction. Recall, from Wikipedia:

Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers. It is done in two steps. The first step, known as the base case, is to prove the given statement for the first natural number. The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number. From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers.

The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

The basis (base case): prove that the statement holds for the first natural number $n$ . Usually, $n=0$ or $n=1$ .

The inductive step: prove that, if the statement holds for some natural number $n$ , then the statement holds for $n+1$ .

The hypothesis in the inductive step that the statement holds for some $n$ is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for $n+1$ .

As an inference rule, mathematical induction can be justified as follows. Having proven the base case and the inductive step, then any value can be obtained by performing the inductive step repeatedly. It may be helpful to think of the domino effect. Consider a half line of dominoes each standing on end, and extending infinitely to the right. Suppose that:

The first domino falls right.

If a (fixed but arbitrary) domino falls right, then its next neighbor also falls right.

With these assumptions one can conclude (using mathematical induction) that all of the dominoes will fall right.

Mathematical induction… works because $n$ is used to represent an arbitrary natural number. Then, using the inductive hypothesis, i.e. that $P(n)$ is true, show $P(k+1)$ is also true. This allows us to “carry” the fact that $P(0)$ is true to the fact that $P(1)$ is also true, and carry $P(1)$ to $P(2)$ , etc., thus proving $P(n)$ holds for every natural number $n$ .

When students first encounter mathematical induction (in either Precalculus, Discrete Mathematics, or Real Analysis), the theorems that students are asked to prove usually fall into four categories:

Calculating a series (examples below).
Statements concerning divisibility (for example, proving that $4$ is always a factor of $5^n-1$ ).
Finding a closed-form expression for a recursively defined sequence (for example, if $a_1 = 4$ and $a_n = 3a_{n-1}$ if $n \ge 2$ , proving that $a_n = 4 \times 3^{n-1}$ )
Statements concerning inequality (for example, proving that $n! > 4^n$ if $n \ge 9$ )

Here’s a common first (or maybe second) example of mathematical induction applied to an arithmetic series.

Theorem. $1^2 + 2^2 + \dots + (n-1)^2 + n^2 = \displaystyle \frac{n(n+1)(2n+1)}{6}$

Proof. Induction on $n$ .

$n = 1$ : The left-hand is simply $1$ , while the right-hand side is $\displaystyle \frac{(1)(2)(3)}{6}$ , which is also equal to $1$ . So the base case works.

$n$ : Assume that the statement holds true for the integer $n$ .

$n+1$ . If I replace $n$ by $n+1$ in the statement of the theorem, then the right-hand side becomes

$\displaystyle \frac{(n+1)[(n+1)+1][2(n+1)+1]}{6} = \displaystyle \frac{(n+1)(n+2)(2n+3)}{6}$

I find it helpful to describe this to students as my target. In other words, as I manipulate the left-hand side, my ultimate goal is to end up with this target. Once I have done that, then I have completed the proof.

If I replace $n$ by $n+1$ in the statement of the theorem, then the left-hand side will now end on $n+1$ instead of $n$ :

$1^2+ 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2$

Notice that we’ve seen almost all of this before, except for the extra term $(n+1)^2$ . So we will substitute using the induction hypothesis, carrying the extra $(n+1)^2$ along for the ride.

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{n(n+1)(2n+1)}{6} + (n+1)^2$

Now our task is, by hook or by crook, using whatever algebraic tricks we can think of to convert this last expression into the target. Most students are completely comfortable doing this, although they typically multiply out the term $n(n+1)(2n+1)$ unnecessarily. Indeed, many early proofs by induction are simplified by factoring out terms whenever possible — in the example below, $(n+1)$ is factored on the third step — as opposed to multiplying them out. In my experience, proofs by induction often serve as a stringent test of students’ algebra skills as opposed to their skills in abstract reasoning.

In any event, here’s the end of the proof:

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{n(n+1)(2n+1)}{6} + (n+1)^2$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{n(n+1)(2n+1) + 6(n+1)^2}{6}$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{(n+1)[n(2n+1) + 6(n + 1)]}{6}$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{(n+1)(2n^2 + n + 6n + 6)}{6}$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{(n+1)(2n^2 + 7n + 6)}{6}$

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 + (n+1)^2 = \displaystyle \frac{(n+1)(n+2)(2n+3)}{6}$

A fair amount of algebra was needed to prove the $n+1$ case. However, the first step — the base case — was especially easy. Indeed, in most proofs by induction seen by students, the base case is often quite trivial… to the point that students often wonder why the base case is needed in the first place.

I first saw this next example in Calculus, by Tom M. Apostol. This next fallacious example illustrates what can happen if the base case is ignored. The statement of this “theorem” doesn’t match the formula for an arithmetic series, and so clearly something is wrong with the following “proof.”

“Theorem.” $1 + 2 + \dots + (n-1) + n = \displaystyle \frac{(2n+1)^2}{8}$

“Proof.” Induction on $n$ .

$n = 1$ : Let’s just ignore the base case, it’s unimportant.

$n$ : Assume that the statement holds true for the integer $n$ .

$n+1$ . If I replace $n$ by $n+1$ in the statement of the theorem, then the right-hand side — my target — becomes

$\displaystyle \frac{[2(n+1)+1]^2}{8} = \displaystyle \frac{(2n+3)^2}{8}$

On the left-hand side, we use the induction hypothesis:

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(2n+1)^2}{8} + (n+1)$

Now our task is, by hook or by crook, using whatever algebraic tricks we can think of to convert this last expression into the target.

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(2n+1)^2}{8} + (n+1)$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(2n+1)^2 + 8(n+1)}{8}$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{4n^2+4n+1+8n+8}{8}$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{4n^2+12n+9}{8}$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(2n+3)^2}{8}$

So that’s the end of the “proof.”

Clearly, something went wrong with the above proof. What went wrong, obviously, is that we didn’t check the base case. If $n=1$ , then the left-hand side is $1$ . However, the right-hand side is $\displaystyle \frac{[(2)(1) + 1]^2}{8} = \displaystyle \frac{9}{8}$ . So the base case is false.

So what happened?

We correctly showed that, if the case $n$ is true, then the case $n+1$ is also true. The catch, of course, is that the case $n$ is never true. Using the domino analogy, we showed that if a domino falls, then the next domino will fall. But the first domino never falls.

All this to say… yes, it’s important to check that the base case actually works.

6 thoughts on “Importance of the base case in a proof by induction”

Pingback: 100,000 page views | Mean Green Math
Pingback: 250,000 page views | Mean Green Math
Maximus Mathematicus says:

September 4, 2020 at 6:17 pm

A simpler fallacious example would have been n + 3 = n + 4.

1. John Quintanilla says:
  
  November 12, 2020 at 7:31 am
  
  You’re right, of course. Pedagogically, I think I prefer Apostol’s example, as the “proof” has the appearance of the types of problems that students would be expected to do for homework. But I suppose my preference is really a matter of taste.
  
James Da Silva Chen says:

September 1, 2021 at 12:58 am

I think you made a typo in the last three lines of your inductive step in your fallacious example. The 6 should be turned into an 8

1. John Quintanilla says:
  
  September 1, 2021 at 8:36 am
  
  Thanks for catching that. It’s now been fixed.

Importance of the base case in a proof by induction

Published by John Quintanilla

6 thoughts on “Importance of the base case in a proof by induction”

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by John Quintanilla

6 thoughts on “Importance of the base case in a proof by induction”

Leave a Reply Cancel reply