Proving theorems and special cases (Part 5): Mathematical induction

Today’s post is a little bit off the main topic of this series of posts… but I wanted to give some pedagogical thoughts on yesterday’s post concerning the following proof by induction.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$ .

$n = 1$ : $5^1 - 1 = 4$ , which is clearly a multiple of 4.

$n$ : Assume that $5^n - 1$ is a multiple of 4, so that $5^n - 1 = 4q$ , where $q$ is an integer. We can also write this as $5^n = 4q + 1$ .

$n+1$ . We wish to show that $5^{n+1} - 1$ is equal to $4Q$ for some (different) integer $Q$ . To do this, notice that

$5^{n+1} - 1 = 5^1 5^n - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$ .

So if we let $Q = 5q +1$ , then $5^{n+1} - 1 = 4Q$ , where $Q$ is an integer because $q$ is also an integer.

My primary observation is that even very strong math students tend to have a weak spot when it comes to simplifying exponential expressions (as opposed to polynomial expressions). For example, I find that even very good math students can struggle through the logic of this sequence of equalities:

$2^n + 2^n = 2 \times 2^n = 2^1 \times 2^n = 2^{n+1}$ .

The first step is using the main stumbling block. Students who are completely comfortable with simplifying $x + x$ as $2x$ can be perplexed by simplifying $2^n + 2^n$ as $2 \times 2^n$ . I attribute this to lack of practice with this kind of simplification in lower grade levels.

Here’s another algoebraic stumbling block that I’ve often seen: at the beginning of the $n+1$ case, some students will make the following mistake:

$5^{n+1} - 1 = 5^1 5^n - 1 = 5 (4q) = 4 (5q) = 4Q$ .

Because these students end with a multiple of 4, they fail to notice that the second equality is incorrect since

$5^1 5^n - 1 \ne 5^1 (5^n - 1)$ .

Again, I attribute this to lack of practice with simplifying exponential expressions in lower grade levels… as well as being a little bit over-excited upon seeing $5^n - 1$ and wishing to use the induction hypothesis as soon as possible.

One thought on “Proving theorems and special cases (Part 5): Mathematical induction”

Proving theorems and special cases (Part 5): Mathematical induction

Published by John Quintanilla

One thought on “Proving theorems and special cases (Part 5): Mathematical induction”

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by John Quintanilla

One thought on “Proving theorems and special cases (Part 5): Mathematical induction”

Leave a Reply Cancel reply