Proof By Mathematical Induction (5 Questions Answered)

Proof by mathematical induction is useful for proving many statements involving the natural numbers.  The best part about this proof method is that the two main steps are always the same.

So, what do you need to know about proof by mathematical induction?  Proof by mathematical induction has 2 steps: 1. Base Case and 2. Induction Step (the induction hypothesis assumes the statement for N = k, and we use it to prove the statement for N = k + 1). Weak induction assumes the statement for N = k, while strong induction assumes the statement for N = 1 to k.

Of course, we don’t need to use proof by induction for every theorem.  For some statements, there is only one case to check.

In this article, we’ll talk about proof by mathematical induction, what it is, and how it works.  We’ll also look at some examples to make the concept clear.

Let’s get started.

What Is Proof By Mathematical Induction?

Proof by mathematical induction means to show that a statement is true for every natural number N (N = 1, 2, 3, 4, …).  For example, we might want to prove that 16^N – 11 is divisible by 5 for each natural number N (more on this later)

Proof by mathematical induction is sometimes called proof by induction (or just “induction” for short).   

A proof by induction has two steps:

• 1. Base Case: We prove that the statement is true for the first case (usually, this step is trivial).
• 2. Induction Step: Assuming the statement is true for N = k (the induction hypothesis), we prove that it is also true for n = k + 1.

There are two types of induction: weak and strong.  The difference lies in what we assume for the induction hypothesis:

• Weak Induction: The induction hypothesis is that the statement is true for n = k.  We use this to prove that the statement is true for n = k + 1.
• Strong Induction: The induction hypothesis is that the statement is true for all n, from n = 1 to n = k.  We use this to prove that the statement is true for n = k + 1.

Strong induction assumes more in the hypothesis, and can make it easier to write a proof.

Why Is It Called Proof By Induction?

One definition of induction is to “find general principles from specific examples”.  When we use proof by induction, we are looking at one specific example (the base step) and a general case (the induction step).

Together, these prove the statement that we are investigating for all natural numbers.

Why Proof By Induction Works

Proof by induction works because we are showing that a statement is true for the first case, and also that if it is true for one case, it is true for the next.

A good analogy is dominoes.  If you set up dominoes close together, you can knock over the first one and the rest will follow.

With induction, the base case is knocking over the first domino.  The induction step is showing that the dominoes are close enough together that each one will knock over the next one.

Another analogy is a ladder or staircase. If you have a ladder or staircase with the steps close together, you can climb the first step and then the second, third, and so forth.

With induction, the base case is taking the first step up the ladder or staircase.  The induction step is showing that the steps on the ladder or staircase are close enough together that you can make the next step safely.

When To Use Proof By Induction

You should use proof by induction when you want to prove a statement for all natural numbers N.  For example, you can use mathematical induction to prove that the sum of the first N integers is N(N + 1) / 2, or:

• 1 + 2 + … + N = N(N + 1) / 2

In a proof that uses induction, the previous step (induction hypothesis) is used to prove the next step (induction step).

You should not use proof by induction for a statement that does not rely on numbered cases or steps.  For example, we would not use induction to prove that f(x) = -x² is continuous at x = 0 (since there is only one “case” to prove).

How To Do Proof By Induction

To do a proof by induction, start with the base case.  This case is usually easy.  It also reassures you that the statement is true for at least one case (which is helpful if you statement is still only conjecture!)

Next, go to the induction step.  Make sure that your assumption is stated correctly, and that you are using it in the proof.

You may need to use strong induction in some cases.  You might also need to use other concepts in your proof – the induction hypothesis alone may not be enough to prove the induction step.

Let’s take a look at some examples of proof by mathematical induction to make the concept clear.

Example 1: Proof By Induction For The Sum Of The Numbers 1 to N

We will use proof by induction to show that the sum of the first N positive integers is N(N + 1) / 2.  That is:

• 1 + 2 + … + N = N(N + 1) / 2

We start with the base case: N = 1.

For the left side, we just get the sum of N = 1, which is 1.

For the right side, we substitute N = 1 into the formula to get:

• N(N + 1) / 2
• =1(1 + 1) / 2
• =2 / 2
• =1

Since the left and right sides of the equation match, we know that statement is true for N = 1, the base case.

Now we move to the induction step.  First, assume the statement is true for N = k.  That is:

• 1 + 2 + … + k = k(k + 1) / 2  [this is the induction hypothesis: we assume this is true]

We want to use the induction hypothesis to prove the statement for N = k + 1.  That is, we want to show:

• 1 + 2 + … + (k + 1) = (k + 1)(k + 2) / 2  [we want to prove this statement]

Let’s look at the left side first.  We want to break it down into two parts, one of which is the induction hypothesis.

That way, we can use the equation given by the induction hypothesis to substitute and simplify:

• 1 + 2 + … + (k + 1)  [left side of the statement we want to prove]
• =(1 + 2 + … + k) + (k + 1)  [split sum into two groups: the first group is 1 to k, and the second is (k + 1) by itself]
• =[k(k + 1) / 2] + (k + 1)  [by the induction hypothesis, 1 + 2 + … + k = k(k + 1) / 2]
• =[k(k + 1) / 2] + [2(k + 1) / 2]  [we need a common denominator of 2 to add, and (k + 1) = 2(k + 1) / 2]
• =[k(k + 1) + 2(k + 1)] / 2]  [add the two numerators, since they have a common denominator]
• =(k + 1)(k + 2) / 2  [factor out (k + 1), which leaves us with (k + 2) as the other factor]

This is exactly what we wanted to show: that 1 + 2 + … + (k + 1) = (k + 1)(k + 2) / 2.  So, the induction step is complete.

So, we have used proof by induction to show that 1 + 2 + … + N = N(N + 1) / 2 for all natural numbers N.

Example 2: Proof By Induction For 16^N – 11 Divisible By 5

We will use proof by induction to show that 16^N – 11 is divisible by 5.  That is:

• 16^N – 11 = 5A for some integer A.

We start with the base case: N = 1.

For the left side, we substitute N = 1, which gives us 16¹ – 11 = 5.

Since 5 = 5*1 (A = 1), we know that the left side is divisible by 5, and so the statement is true for N = 1, the base case.

Now we move to the induction step.  First, assume the statement is true for N = k.  That is:

• 16^k – 11 = 5A for some integer A  [this is the induction hypothesis: we assume this is true]

We want to use the induction hypothesis to prove the statement for N = k + 1.  That is, we want to show:

• 16^k+1 – 11 = 5B for some integer B  [we want to prove this statement]

Let’s look at the left side first.  We want to break it down into two parts, one of which is the induction hypothesis.

That way, we can use the equation given by the induction hypothesis to substitute and simplify:

• 16^k+1 – 11  [left side of the statement we want to prove]
• =16*16^k – 11  [16^k+1 = 16*16^k, by rules of exponents]
• =16*(16^k – 11 + 11) – 11  [adding -11 and 11 is the same as adding zero]
• =16*(5A + 11) – 11  [16^k – 11 = 5A by the induction hypothesis]
• =80A + 176 – 11  [distribute the 16 through parentheses]
• =80A + 165
• =5(16A + 33)  [factor out a 5]
• =5B  [where B = 16A + 33, which is an integer since A is an integer]

This is exactly what we wanted to show: that 16^k+1 – 11 = 5Bfor some integer B.  So, the induction step is complete.

So, we have used proof by induction to show that 16^N – 11 is divisible by 5 for all natural numbers N.

Conclusion

Now you know a little more about proof by mathematical induction, what it means, and how it works.  You also have some examples to work with so that you can try writing some proofs of your own.

You might also want to learn more about proof by contradiction in my article here.

I hope you found this article helpful.  If so, please share it with someone who can use the information.

Don’t forget to subscribe to my YouTube channel & get updates on new math videos!

~Jonathon