I’ve had a request to put up a post on induction, since a few people are having trouble with it. Every year people have trouble with induction, perhaps because it’s one of the first methods of formal proof that you see, but hopefully I’ll be able to convince you it really isn’t too bad! The post got pretty long, so I’m going to add the examples as comments at the end, so you can skip down to them if you want.
So what is induction? Well let’s say I have to prove a statement about infinitely many things at once, perhaps a statement about each number . We’ve seen from previous posts that we can’t just check a few examples, we’re interested in a proof that will always hold, so what can we do? The principle of mathematical induction says the following:
Let’s say we know the following two things:
- A statement is true for some base number (let’s assume this is for now)
- Whenever the statement is true for one number , it is also true for
then it follows that the statement is true for all the numbers .
The principle works like lining up a set of dominoes to knock down. If we know (1) that we can knock over the first domino, and (2) that each domino will hit the next one, then we can infer that all the dominoes will fall down. In the mathematical setting, the first part is called the inductive base, and the second part the inductive step.
If you’re first starting out with induction, you might be a bit dubious here. We want to prove a statement is true, and in step (2), we just assume it’s true, and use that to prove it’s true, there must be something dodgy! Actually, the difference is subtle, but an important part of university mathematics. The difference is in the “for all” vs. “for some” wording which may have come up in other places too. We want to prove a statement for all , and to do that, in step (2) we assume the statement is true for some . “For some” just means we assume we can find one place where the statement holds, and induction is a method for starting with one place where something works, and using that to find other places.
Remember: Both ingredients in induction are important. If you only prove the base case, then all you’ve done is proved one special case. If you only prove the step from to , then for all you know, there might not be a place where that statement is true from which you can construct the other places. It’s like lining up all your dominoes, but not checking you can actually push the first one over.
The examples are now below as comments, but before we go on I’ll just remind you of some notation. We’ll often write “P(n)” for “the statement we’re trying to prove about n”, and it’s important to remember that even though it looks like a mathematical expression, P(n) is a statement. For this reason, P(n) can be true, or false, but it doesn’t really make sense to write things like “” .