Proof by Induction Examples

If we're trying to prove inductively that 4n + 1 is always an odd number when n is a positive integer, what should our base case look like?

Before we dig into the meat of an inductive proof, we always wanna test out our general statement on a nice, easy value.

In this case, the problem tells us that n can be any positive integer. The easiest value in that set is probably n = 1, so we'll go with that. Plug it in, plug it in.

4(1) + 1 = 5

Yep, 5 is totally an odd number, so we've just proven our base case. That's all there is to it.

If we're trying to prove inductively that 4n + 1 is always an odd number when n is a positive integer, what's our induction hypothesis?

This is the kinda-weird-but-surprisingly-easy step. We just need to assume that our statement is true when n = k, so all we've gotta do is plug in k for n:

4k + 1 is an odd number.

Dunzo.

Once we've proven our base case and made our induction hypothesis, what's our final step in proving inductively that 4n + 1 is always an odd number when n is a positive integer? (You don't need to actually work through the proof yet—just explain the finishing move.)

To finish up, we need to prove that 4(k + 1) + 1 is always an odd number. All we're really doing is replacing the k with k + 1 in our assumed 4k + 1.

Then we'll rearrange our brand-spanking-new expression so that our original 4k + 1 shows up somewhere in there. Finally, we'll use that to prove the new expression 4(k + 1) + 1 is odd, no matter what integer we plug in for k. Once we've done that, we'll be inducted into the Induction Hall of Fame.