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

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct. In the previous two posts, we saw that a statement that’s true for the first 40 cases or even the first 10^{316} cases may not be true for all cases.

This is the reason that mathematical induction is important, as it provides a way to build from previous cases to prove that the next case is still correct, thus proving that all cases are correct.

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^n 5^1 - 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.

QED

In the above proof, we were able to build from the n case to reach the n +1 case. In this sense, to answer the student’s question, it is possible to prove a theorem by first proving a special case of the theorem.

By contrast, when trying to “prove” that n^2 - n + 41 is prime for all integers n, the proposition is true for 1 \le n \le 40, but it’s just a coincidence… there was no string of logic that connected these first 40 cases other than the coincidence that they all were correct.

 

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: