Proof by Induction at a Glance

Deduction is all about going from general theories to specific examples. Induction flips this whole shebang around, like a fun-house mirror. Inductive proofs go from the bottom up: we start with a specific statement and use it to prove a general theory.

Let's revisit our Ten Commandments example. Say you'd never heard the rule "thou shalt not steal" before, but then you noticed that you felt kinda bad after taking your buddy's Xbox without his permission. He probably got really mad at you, if the steam shooting out of his ears was any indication.

Using inductive reasoning, you could go from the specific ("stealing this Xbox was a bad idea") to a general theory ("hey guys, let's maybe not steal anything anymore"). It reverses the deductive direction.

We usually use induction to prove mathematical statements involving a variable (typically n) for all integer values of n, or sometimes just positive integer values. For example, we might want to prove that 2n is always an even number when n is any integer.

That's all fine and well, but what does induction mean for an actual algebra proof? Here's how mathematical induction works in three easy(ish) steps.

1. Prove the base case. In other words, show that when n = 1 (or some easy number in our set), the claim is true.
2. Assume the statement is true for n = k. This is called the induction hypothesis.
3. Prove that the statement is true when n = k + 1.

Let's look at each of 'em in a bit more detail.

1. Prove the base case.

First, we test our claim out on a small, easy value to see if it even works at all. For example, say we're trying to prove the general theory that 2n is always an even number when n is any positive integer.

We'd start out by plugging in n = 1, because it's easy, we're lazy, and it's the first positive integer.

2(1) = 2

Yep, 2 is even. We just proved our base case, which means our statement is true for at least that one value. Remember, inductive proofs start from the bottom, like Drake. Specific to general. Example to theory. It sounds out there, but it works.

By the way, one funny quirk of inductive proofs is that a single counterexample will ruin the entire proof. A counterexample is any value of n that makes the statement not true. If there's even one measly counterexample, then the general statement or theory can't possibly be true.

2. Induction hypothesis: assume the statement is true for n = k.

This is probably both the easiest and weirdest step, because it involves some Peter Pan-style make-believe. All we're doing here is swapping out the general term, n, for k, which stands for a specific term. Except we don't even need to pick an actual number. Literally just replace n with k in our original statement. For example:

2k is an even number.

Sure, it's an assumption, but we already know it's true for at least one specific number: the base case. We're just laying the groundwork here; we'll see why in a sec.

3. Prove that the statement is true when n = k + 1.

This is where the real meat of the proof comes in. Since we're already assuming our statement is true for n = k, now we need to prove that it's also true for the next integer, k + 1. If we can prove that, then we can prove the general theory.

In our example, now we'd replace k with k + 1:

2(k + 1) is an even number.

How do we prove that? The strategy will depend on the specific proof, but we usually want to manipulate our expression until the induction hypothesis n = k case shows up somewhere (that's the assumption that we "proved" in step 2). Let's multiply it out real quick.

2(k + 1) = 2k + 2

Now we're trying to prove that 2k + 2 is even. But hey, we already know that 2k is even from our assumption earlier. So it really looks like this:

2k + 2 = (even number) + 2

What happens when we add 2 to an even number? We always get another even number as our answer, that's what. Try it out:

2 + 2 = 4 (even)
6 + 2 = 8 (also even)
380 + 2 = 382 (yep, still even)

It's all even, all the time. There aren't any possible counterexamples where adding 2 to an even number doesn't give us an even number, so it must be true for all values of k.

We just proved that 2(k + 1) is an even number. Let's break down what exactly we've done.

We started out by proving that our statement was true for n = 1. We could also think of this as k = 1, since k can be any integer we want it to. From there, since we went from k to k + 1 and it worked just fine, we could run the whole proof again and again by adding 1 over and over. We're not gonna, but we could. If 2k is even, then 2(k + 1) is even, which means 2(k + 2) is even, which means 2(k + 3) is even, and so on for every possible positive integer, forever and ever, which means our original statement is true:

2n is always an even number when n is any positive integer.

Pretty tricky, right? We used one very specific statement to prove a general theory. We proved that the base case was true, and then we showed that every case after that would be true too, as long as we started with a true statement.

That example was at the shallow end of the pool, though. In the next section, we'll use these steps to dive into the deep end with a slightly harder proof. Better grab your sunscreen and water wings.