Mathematical Induction: Proof by Induction

Written by

Malcolm McKinsey

January 12, 2023

Fact-checked by

Paul Mazzola

Mathematical induction

We hear you like puppies. We are fairly certain your neighbors on both sides like puppies. Because of this, we can assume that every person in the world likes puppies.

That seems a little far-fetched, right? But mathematical induction works that way, and with a greater certainty than any claim about the popularity of puppies.

Before we can claim that the entire world loves puppies, we have to first claim it to be true for the first case. In logic and mathematics, a group of elements is a set, and the number of elements in a set can be either finite or infinite.

Yet all those elements in an infinite set start with one element, the first element.

Proving some property true of the first element in an infinite set is making the base case. In the silly case of the universally loved puppies, you are the first element; you are the base case, n. You love puppies.

Proof by induction

Your next job is to prove, mathematically, that the tested property P is true for any element in the set -- we'll call that random element k -- no matter where it appears in the set of elements.

This is the induction step. Instead of your neighbors on either side, you will go to someone down the block, randomly, and see if they, too, love puppies.

So what was true for (n)=1 is now also true for (n)=k. Another way to state this is the property (P) for the first (n) and (k) cases is true:

The next step in mathematical induction is to go to the next element after k and show that to be true, too:

If you can do that, you have used mathematical induction to prove that the property P is true for any element, and therefore every element, in the infinite set. You have proven, mathematically, that everyone in the world loves puppies.

Mathematical induction steps

Those simple steps in the puppy proof may seem like giant leaps, but they are not. Many students notice the step that makes an assumption, in which P(k) is held as true. That step is absolutely fine if we can later prove it is true, which we do by proving the adjacent case of P(k + 1). All the steps follow the rules of logic and induction.

Mathematical induction works if you meet three conditions:

1. For the questioned property, is the set of elements infinite?

2. Can you prove the property to be true for the first element?

3. If the property is true for the first k elements, can you prove it true of k+1?

So, while we used the puppy problem to introduce the concept, you can immediately see it does not really hold up under logic because the set of elements is not infinite: the world has a finite number of people. The puppies helped you understand the steps.

Mathematical induction proof

Here is a more reasonable use of mathematical induction:

So our property P is:

Go through the first two of your three steps:

1. Is the set of integers for n infinite? Yes!

2. Can we prove our base case, that for n=1, the calculation is true?

Yes, P(1) is true! We have completed the first two steps. Onward to the inductive step!

Assume for a moment that P(k) is true:

That means ${k}^{3}+2k=3z$where z is a positive integer.

Now the audacious next step:

Assuming ${k}^{3}+2k$ is divisible by $3$, we show that ${\left(k+1\right)}^{3}+2\left(k+1\right)$ is also divisible by three:

Replace the expression ${k}^{3}+2k$ with $3z$:

Now factor the 3 out:

Which means the expression ${\left(k+1\right)}^{3}+2\left(k+1\right)$ is divisible by 3.

This makes the original proposition about the property true, since it was shown for P(1), P(k) and P(k+1).

Checking your work

Mathematical induction seems like a slippery trick, because for some time during the proof we assume something, build a supposition on that assumption, and then say that the supposition and assumption are both true. So let's use our problem with real numbers, just to test it out.

Remember our property: ${n}^{3}+2n$ is divisible by 3. First, we'll supply a number, 7, and plug it in:

The rule for divisibility by 3 is simple: add the digits (if needed, repeatedly add them until you have a single digit); if their sum is a multiple of 3 (3, 6, or 9), the original number is divisible by 3:

Take the 1 and the 5 from 15 and add:

Now you try it. Think of any number (use a calculator if you need to) and plug it in:

Did it work?

Proof by induction examples

If you think you have the hang of it, here are two other mathematical induction problems to try:

1) The sum of the first n positive integers is equal to $\frac{n(n+1)}{2}$

We are not going to give you every step, but here are some head-starts:

• Base case: $P(1)=\frac{1(1+1)}{2}$. Is that true?

• Induction step: Assume $P(k)=\frac{k(k+1)}{2}$

2) ${1}^{3}+{2}^{3}+{3}^{3}+...+{n}^{3}=\frac{{n}^{2}(n+1{)}^{2}}{4}$

• Base case: $P(1)={1}^{3}=\frac{{1}^{2}(1+1{)}^{2}}{4}$

• Induction step: Assume $P(k)={1}^{3}+{2}^{3}+{3}^{3}...+{k}^{3}=\frac{{k}^{2}(k+1{)}^{2}}{4}$

Lesson summary

Now that you have worked through the lesson and tested all the expressions, you are able to recall and explain what mathematical induction is, identify the base case and induction step of a proof by mathematical induction, and learn and apply the three steps of mathematical induction in a proof which are the base case, induction step, and k + 1.