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.

green lineMy 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.

Leave a comment

1 Comment

  1. Proving theorems and special cases: Index | Mean Green Math

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: