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:
2^1 >= 1^2 because 2 > 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
2^(n+1) = 2 * 2^n and (n+1)^2 = n^2 + 2n + 1, so we are really trying to prove that 2 * 2^n >= n^2 + 2n + 1.2^n + 2^n >= n^2 + (2n + 1)2^n >= 2n + 1 because this is true when n = 2, and the left hand side clearly grows faster than the right hand side (Yes! You can write this out as another formal proof by induction, but I’m skipping it for clarity).2^n + 2^n >= n^2 + (2n + 1). This is equivalent to what we were trying to show.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.