Induction in Action Examples

Prove inductively that 4n + 1 is always an odd number when n is a positive integer.

Here it is. The big leagues. We're finally ready to rock our own inductive proof. Let's do this thing.

First, we prove our base case:

When n = 1, we get 4(1) + 1 = 5, which is an odd number.

Beautiful. Now we assume our general statement is true when n = k:

4k + 1 is an odd number.

Next up, we replace k with k + 1:

Is 4(k + 1) + 1 an odd number?

We've got to prove this new statement is true. For starters, let's distribute that 4:

4(k + 1) + 1 = 4k + 4 + 1

Don't combine those constants just yet, though. We're already assuming that 4k + 1 is an odd number, so let's rearrange our new expression in a way that contains 4k + 1.

4k + 4 + 1 = (4k + 1) + 4

There we go. Since we "know" that 4k + 1 is odd, we can think of our expression like this:

(4k + 1) + 4 = (odd number) + 4

What happens when we add 4 to an odd number? The same thing that happens when we add any even number to an odd number:

odd + even = odd

Go ahead and test this baby out with a few values.

3 + 4 = 5
7 + 4 = 11
11 + 4 = 15
835 + 4 = 839

See? Our sum is always odd. So since 4k + 1 is an odd number and 4 is an even number, we'll always, always get an odd sum when we add 'em.

(odd number) + 4 = odd number

There aren't any possible counterexamples, so (4k + 1) + 4 is always an odd number. We proved it's true for k + 1, which means our original statement is also true: 4n + 1 always equals an odd number when n is a positive integer.

Prove inductively that n < n² when n is any positive integer greater than 1.

We're on the case. The base case, that is. Sadly, n needs to be a positive integer bigger than 1, so we can't use our old standby, n = 1. Let's go with n = 2 instead.

2 < 2²
2 < 4

Yeah, that's true—2 is definitely smaller than 4. Our base case is proven. Next up, it's assumption time. For our induction hypothesis, we plug in n = k:

k < k²

From here on out, we'll treat that inequality as true. Now replace those k's with k + 1:

k + 1 < (k + 1)²

Good deal. Let's expand that squared binomial.

k + 1 < k² + 2k + 1

Now what? The name of the game is getting our induction hypothesis into the mix somehow. It's not a great name for a game, but oh well. We can subtract 1 from both sides.

k < k² + 2k

All right, we already "know" that k is less than k² from our induction hypothesis. In other words, the stuff on the left is smaller than the stuff on the right in the expression k < k². Since k is a positive integer, adding 2k to the right side is going to make that side bigger than it was before, right? A positive plus a positive is always a bigger positive. So k must also be less than k² + 2k. We made the right side larger but kept the left side like it was.

Or think of it this way:

k + 0 < k² + 2k

We know k < k², and we know 0 < 2k because zero is smaller than any positive number. That means both terms on the left are less than both terms on the right.

Therefore, n < n² for all positive integers greater than 1. There's our proof.