Proof by Induction

Suppose that I wanted to prove that something is true for all natural numbers n. Since there are infinitely many such numbers, I can’t prove the statement individually for all the numbers, so what can I do?

The answer: Induction. A proof by induction works like this - prove that it’s true when n = 1, and then prove that if it’s true for n, it’s true for n + 1. Therefore it’s true for 1, for 1+1, for 1+1+1, etc.

Let’s put actual numbers on this vague explanation. Let’s prove that 2^n >= n^2 for all n in the natural numbers.

First, I’ll show that it’s true for 1:

Now, I’ll show that if we assume 2^n >= n^2 (where n >= 2), we can prove 2^(n+1) >= (n+1)^2

So now we’ve proven our original statement (2^n >= n^2) true for all natural numbers by the principle of mathematical induction.

I could give you a bunch more examples, but the concept itself is pretty simple. First, prove a base case, usually n = 1. Then prove an inductive case, where you assume that it was true for the previous number, and prove it for the next number.