"There are actually two forms of induction, the weak form and the strong form. Let’s look at the weak form first. It says: 1. If a predicate is true for a certain number, 2. and its being true for some number would reliably mean that it’s also true for the next number (i.e., one number greater), 3. then it’s true for all numbers. All you have to do is prove those two things, and you’ve effectively proven it for every case. The first step is called the base case, and the “certain number” we pick is normally either 0 or 1. The second step, called the inductive step, is where all the trouble lies. You have to look really, really carefully at how it’s worded, above. We are not assuming that the predicate is true for any old number! We are simply considering, if it’s true for any old number, whether that would necessarily imply it’s also true for the next number. In terms of the predicate, we’re asking “does P(k) imply P(k + 1)?” In other words: “we aren’t sure if P(k) is true. But if it is — a big “if,” of course — would that logically demand that P(k + 1) was also true?” If you can prove that it does, then you’re in business. The whole thing is set up like a row of dominos. If one domino falls, then the one after it will also fall. And if that one falls, then so will the next. All that is needed is a base case to tip over the first domino, and by this trail of causality, all the dominos will fall. One terminology note: the entire second step is called the inductive step, but the first half of it (the part where we assume that P(k) is true) is called the inductive hypothesis. We never prove the inductive hypothesis; rather, we assume it, and then see if that allows us to deduce that P(k + 1) would also be true. Let’s work this out for the drinking/voting example. Let Vote(n) be the proposition that a citizen of age n can vote. Our proof goes like this: 1. base case. Vote(21) is true, because a 21-year old is old enough to vote in the state and national elections. 2. inductive step. Vote(k) ⇒ Vote(k+1). Why? Because nobody’s gettin’ any younger. If you can vote in a particular year, then you’re also old enough to vote next year. Unless the laws change, there will never be a case when someone old enough to vote this year turns out to be too young to vote next year. 3. conclusion. Wow. ∀ n ≥ 21 Vote(n). We’re done. Q.E.D. and all that. The only specific example we showed was true was Vote(21). And yet we managed to prove Vote(n) for any number n ≥ 21. Let’s look back at that inductive step, because that’s where all the action is. It’s crucial to understand what that step does not say. It doesn’t say “Vote(k) is true for some number k.” If it did, then since k’s value is arbitrary at that point, we would basically be assuming the very thing we were supposed to prove, which is circular reasoning and extremely unconvincing. But that’s not what we did. Instead, we made the inductive hypothesis and said, “okay then, let’s assume for a second a 40-year-old can vote. We don’t know for sure, but let’s say she can. Now, if that’s indeed true, can a 41-year-old also vote? The answer is yes.” We might have said, “okay then, let’s assume for a second a 7-year-old can vote. We don’t know for sure, but let’s say she can. Now, if that’s indeed true, can an 8-year-old also vote? The answer is yes.” Note carefully that we did not say that 8-year-olds can vote! We merely said that if 7-year-olds can, why then 8-year-olds must be able to as well. Remember that X ⇒ Y is true if either X is false or Y is true (or both). In the 7/8-year-old example, the premise X turns out to be false, so this doesn’t rule out our implication. The result is a row of falling dominos, up to whatever number we wish. Say we want to verify that a 25-year-old can vote. Can we be sure? Well:"