Writing Better Proofs Part 4: Induction

Of all the types of proof, proof by induction is the one I see botched the most often.

Induction proofs are a very specific type of proof with some very specific requirements. Failing to cover all of the requirements, at best is not a complete proof, and at worst will result in fatal flaws in the argument.

Anatomy of an Induction Proof

All induction proofs need to have the same basic steps:

1. A clear definition of the statement to be proved using induction

All proofs should be clear about what what they are tying to prove, but in the case of induction proofs this is even more important. Consider the following problem

Problem Show that the vectors \(\{v_1,\ldots,v_n\}\) are linearly independent.

We might perform an induction argument to show that for each \(1\le m\le n\), the vectors \(\{v_1,\ldots,v_m\}\) are linearly independent. However, note that this is subtly different from the result we are asked to prove, which is in fact a special case \(m=n\) of this more general statement¹.

We might then start our solution:

We will show \(\{v_1,\ldots,v_m\}\) are linearly independent for all \(1\le m\le n\). The result clearly follows from the case \(m=n\). We proceed by induction…

This final sentence shows how the induction proof suffices for our problem.

2. A base case

All induction proofs need a starting point and a base case is that point. Be clear about what it is and why the statement holds true in that case. Continuing the example above we might say

Our base case is \(m=1\). Note that \(v_1\neq 0\) and so \(\{v_1\}\) is a linearly independent set.

Note that we don’t have to start at a minimum value: if we only need to prove a fact for \(n>5\), taking a base case of \(n=6\) is perfectly valid.

3. An assumption that the statement holds in some case

Critical to the layout of an induction proof is the instruction to “assume the statement holds when…”. You are trying to prove that the statement holding in one case implies it holds in another. If you do not make the assumption clear, you must make it clear that you have achieved this after the next step.

4. A proof that if the assumption holds in one case, it holds in another case

This is the main meat of the solution and most often is the only part of an induction proof to survive the long journey from brain to page.

Despite being the crux of the problem, simply presenting a proof of an inductive step is not a full inductive proof.

5. A proof that the induction is well founded

This is the only step that can be omitted and can only be done so if it is trivial. However, it is also the most subtle.

Induction lives and dies by its well foundedness. The subtleties are beyond the scope of this note, but in short you need to show that your inductive step terminates after a finite number of steps in a base case.

Consider, as a bad example the following “proof”, where induction for every \(n\) doesn’t terminate in the base case.

All numbers are even. Indeed, we prove this by (strong) induction. The base case is the number \(0\) which is trivially even. Now assume that all numbers less than \(n\) are even. In particular then, \(n-2\) is even. But if we sum two even numbers (and \(2\) is surely even) we have an even number. Hence \(n\) is even.

Thus by mathematical induction, \(n\) is even for all \(n\).

In 99% of cases this step will be unnecessary, but when it fails, it can do so spectacularly.

You may think that once you’ve written one induction proof you’ve written them all, but they can be trickier to pull off than expected.

This is part of a series on writing better proofs. The pages in the series are not static and will be updated and improved as time goes on. If you have comments or suggestions, please email me. I’d be particularly interested in hearing if you disagree with me or have suggestions for topics to cover.