All this talk about mathematical induction might sound pretty abstract at first, so let's run through another specific example, yeah? Actually, let's walk through it, nice and slow-like.
Sample Problem
Use mathematical induction to prove that 5n + 1 is always an even number when n is any positive integer.
Can we use our new inductive chops to make this happen? You bet. Just remember those three basic steps:
- Prove the base case. In other words, show that when n = 1 (or some easy number in our set), the claim is true.
- Induction hypothesis: assume the statement is true for n = k.
- Prove that the statement is true when n = k + 1.
Let's start with the base case. Since n can be any positive integer in the known universe, we'll go with a nice, small value to make things easy: n = 1. Let's plug it in and see what happens.
51 + 1 = 5 + 1 = 6
Hey, look at that: 6 is definitely an even number, so our base case is true. That means we're in the clear and we can move on to the actual induction. Ready?
Now it's hypothesis time. We're gonna make the assumption that our claim is true when n = k. We don't actually know that's true for sure, but it's cool—inductive proofs always have an assumption like this in the middle. That means we can just swap out our n for a k:
5k + 1 is an even number.
This is probably the easiest part of the whole proof. Now comes the last step: we need to prove that the claim is also true for the next integer: k + 1. So we replace our k with k + 1.
5(k + 1) + 1
Now we just need to prove that this expression is also an even number. A good trick for doing this is to mess with our expression until the original n = k case shows up somewhere (since we already know that's even, from our induction hypothesis above), along with some other part of the expression we can also prove is an even number. Here we go.
First, let's split 5(k + 1) into two parts, using our handy exponent rules:
5(k + 1) + 1 = 5(5k) + 1
See what we did there? Since multiplying the same base means adding the exponents together (like how x2x3 = x(2 + 3) = x5), we can turn 5(k + 1) into 5(5k). So far, so good.
But remember, we wanna get our original 5k + 1 expression into the mix somehow. So what if we split up the 5(5k) part into two more pieces? If we think of that first 5 as a coefficient, we can split it into 4 + 1, right? For example, if we had 5x, we could split that into 4x + x. Well, just think of that x as 5k instead, and we can do 5(5k) = (4 + 1)5k = 4(5k) + 5k. It looks kinda gnarly, but it's the same exact thing. Let that sink in for a sec if you need to.
Now let's see what that does to our entire expression.
5(5k) + 1 = 4(5k) + 5k + 1
Hey, lookie there—we've got the original 5k + 1 on the right side. That means we're really dealing with two parts here: 4(5k) and 5k + 1. We already know the second half, 5k + 1, is an even number, since we "proved" it earlier. But what about 4(5k)?
Here's the thing: if we multiply 4 by any integer in the world, we're gonna get an even number back. Or to put it in fancy math-terms, the product of 4 and any integer will itself be a factor of 4, and all factors of 4 are even. Go ahead and try it out:
4 × 3 = 12
4 × 7 = 28
4 × 16 = 64
4 × 1,000,000 = 4,000,000
Yep, all even numbers. That means 4(5k) is always even too, no matter what 5k is. So both halves of our expression—4(5k) and 5k + 1—are even numbers, all the time. But we also learned a handy little theorem back in our early algebra days: the sum of two even numbers is always another even number. Remember that? We can check that baby out, too:
2 + 4 = 6
18 + 32 = 50
98 + 632 = 730
No matter which two even numbers we start with, we'll always get another even number as our sum. There aren't any counterexamples. And that means that the sum of 4(5k) and 5k + 1 is gonna be even, since both 4(5k) and 5k + 1 are even numbers on their own.
4(5k) is even,
5k + 1 is even,
therefore 4(5k) + (5k + 1) is even.
Boom! We just proved that our claim is true for n = k + 1, so we've proven that 5n + 1 is always an even number.
You may be asking yourself, how did what we did actually prove the statement? Think of it this way: we showed that if the statement is true for one integer, it's true for the next integer as well. Since we know the statement is true for n = 1 (that was our base case) it must now be true for n = 2 as well. Now that we know it's true for n = 2, it must be true for the next integer, 3. We can play this game all day long. The pattern continues, so the statement is true for every whole number.
We can use induction to prove all kinds of theorems and rules in math. What it basically tells us is that if we knock over the first domino in a set of dominoes, then the rest of the dominoes will fall down also. Now if we can only find someone to pick up the dominoes once we're through with them.