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 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 is a positive integer, then is a multiple of 4.

Proof. By induction on .

: , which is clearly a multiple of 4.

: Assume that is a multiple of 4, so that , where is an integer. We can also write this as .

. We wish to show that is equal to for some (different) integer . To do this, notice that

by the induction hypothesis

.

So if we let , then , where is an integer because is also an integer.

QED

In the above proof, we were able to build from the case to reach the 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 is prime for all integers , the proposition is true for , 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.