# 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.