Mathematical Induction for Divisibility

In this lesson, we are going to prove divisibility statements using mathematical induction. If this is your first time doing a proof by mathematical induction, I suggest that you review my other lesson which deals with summation statements. The reason is students who are new to the topic usually start with problems involving summations followed by problems dealing with divisibility.

Steps to Prove by Mathematical Induction

1. Show the basis step is true. That is, the statement is true for n=1.
2. Assume the statement is true for n=k. This step is called the induction hypothesis.
3. Prove the statement is true for n=k+1. This step is called the induction step

What does it mean by a divides b ?

Since we are going to prove divisibility statements, we need to know when a number is divisible by another. So how do we know for sure if one divides the other?

Suppose \color{blue}\Large{a} and \color{blue}\Large{b} are integers. If \color{blue}\Large{a} divides \color{blue}\Large{b} , then we can write it as an equation

where \color{red}\Large{c} is some integer.

Let’s go over some concrete examples.

• 2 divides 10 because 10=2{\color{red}(5)} where \color{red}5 is an integer
• 8 divides 136 because 136=8{\color{red}(17)} where \color{red}17 is an integer
• 11 divides 143 implies 143=11{\color{red}(13)} where \color{red}13 is an integer
• 17 divides 323 implies 323=17{\color{red}(19)} where \color{red}19 is an integer

Examples of Proving Divisibility Statements by Mathematical Induction

Example 1: Use mathematical induction to prove that \large{n^2} + n is divisible by \large{2} for all positive integers \large{n}.

a) Basis step: show true for n=1.

{n^2} + n = {\left( 1 \right)^2} + 1

= 1 + 1

= 2

Yes, 2 is divisible by 2.

b) Assume that the statement is true for n=k. Thus, {n^2} + n becomes {k^2} + k where k is a positive integer.

Now, write {k^2} + k as part of an equation which denotes that it is divisible by 2.

{k^2} + k = 2x

for some integer x.

Solve for \color{red}k^2. We will use this for substitution later.

{\color{red}{k^2}} = 2x - k

c) Prove the statement is true for n=k+1.

Where y = x + k + 1, and since x and k are integers, therefore y is also an integer.

This means that {\left( {k + 1} \right)^2} + \left( {k + 1} \right) is also divisible by 2.

\therefore By principle of mathematical induction, the statement is true for all positive integers.

Example 2: Use mathematical induction to prove that \large{n^3} - n + 3 is divisible by \large{3} for all positive integers \large{n}.

a) Is it true for n=1?

{n^3} - n + 3 = {\left( 1 \right)^3} - \left( 1 \right) + 3

= 1 - 1 + 3

= 3

Yes, it is divisible by 3.

b) Assume true for n=k.

{n^3} - n + 3{k^3} - k + 3 where k \in \mathbb{Z}^+

Next, express {k^3} - k + 3 as part of an equation which suggests that it is divisible by 3.

{k^3} - k + 3=3x

for some integer x

Solve for \color{red}k^3. This will be used for substitution later.

{\color{red}{k^3}} = 3x + k - 3

c) Show that the statement is true for n=k+1.

Notice, y = x + {k^2} + k. Since x and k are integers, then y must also be an integer.

We have shown that {\left( {k + 1} \right)^3} - \left( {k + 1} \right) + 3 is divisible by 3.

\therefore By the principle of mathematical induction, the statement is true for all positive integers.

Example 3: Use mathematical induction to prove that \large{2^{2n}} - 1 is divisible by \large{3} for all positive integers \large{n}.

a) Basis step: show the statement is true for n=1.

{2^{2n}} - 1 = {2^{2\left( 1 \right)}} - 1

= {2^2} - 1

= 4 - 1

= 3

Yes, it is divisible by 3.

b) Assume the statement is true for n=k.

Substitute k for n to transform \large{2^{2n}} - 1 to \large{2^{2k}} - 1.

Suppose k is a positive integer, if \large{2^{2k}} - 1 is divisible by 3 then there exists an integer x such that

\large{2^{2k}} - 1 = 3{\color{blue}x}

Let’s solve for \large\color{red}{2^{2k}}. This will be used in our inductive step in part c.

\large{\color{red}{2^{2k}}} = 3x + 1

c) Prove the statement true for n=k+1.

Note, y=4x+1. I hope you can see that y is an integer since x is also an integer.

Clearly, \large{2^{2\left( {k + 1} \right)}} - 1 is divisible by 3.

\therefore By the principle of mathematical induction, the statement is true for all positive integers.

Example 4: Use mathematical induction to prove that \large{9^n} + 3 is divisible by \large{4} for all positive integers \large{n}.

a) Is it true for n=1?

\large{9^n} + 3 = {9^1} + 3

\large = 9 + 3

\large = 12

Yes, 12 is divisible by 4.

b) Assume the statement is true for n=k.

Replace n by k, thus we have \large{9^k} + 3. Now, write \large{9^k} + 3 in an equation showing that it is divisible by 4.

Suppose k is a positive integer, if \large{9^k} + 3 is divisible by 4 then there exists an integer x such that

\large{9^k} + 3 = 4{\color{blue}x}

Solve for \large\color{red}{9^k}.

\large{\color{red}{9^k}} = 4x - 3

c) Prove the statement true for n=k+1.

Where y = 9x - 6 and y is an integer because x is some integer.

This means \large{9^{k + 1}} + 3 is divisible by 4.

\therefore By the principle of mathematical induction, the statement is true for all positive integers.

Example 5: Use mathematical induction to prove that \large{8^n} - {3^n} is divisible by \large{5} for all positive integers \large{n}.

a) Basis step: show true for n=1.

\large{8^n} - {3^n} = {8^1} - {3^1}

\large = 8 - 3

\large = 5

Yes, it is divisible by 5.

b) Assume the statement is true for n=k.

Transform \large{8^n} - {3^n} to \large{8^k} - {3^k}.

Write \large{8^k} - {3^k} in an equation expressing that it is divisible by 5.

\large{8^k} - {3^k}=5{\color{blue}x}

for some positive integer x

Solve for \large\color{red}{8^k}. We will use this for substitution in part c.

\large{\color{red}{8^k}} = 5x + {3^k}

c) Prove the statement is true for n=k+1.

where \large{y={8x + {3^k}}}

y is some integer since x and k are integers

We have shown that \large{8^{k + 1}} - {3^{k + 1}} is divisible by 5.

\therefore By the principle of mathematical induction, the statement is true for all positive integers.

Example 6: Use mathematical induction to prove that \large{5^{2n - 1}} + 1 is divisible by \large{6} for all positive integers \large{n}.

a) Basis step: show true for n=1.

\large{5^{2n - 1}} + 1 = {5^{2\left( 1 \right) - 1}} + 1

\large = {5^{2 - 1}} + 1

\large = {5^1} + 1

\large = 5 + 1

\large = 6

Yes, it is divisible by 6.

b) Assume true for n=k. We have \large{5^{2k - 1}} + 1.

Write \large{5^{2k - 1}} + 1 in an equation expressing that it is divisible by 6.

\large{5^{2k - 1}} + 1 = 6{\color{blue}x}

for some integer x

Solve for \large\color{red}{5^{2k}}.

c) Prove the statement is true for n=k+1.

where y = 25x - 4

Obviously y is an integer since x is also an integer

Clearly, \large{5^{2\left( {x + 1} \right) - 1}} + 1 is divisible by 6.

\therefore By the principle of mathematical induction, the statement is true for all positive integers.

Example 7: Use mathematical induction to prove that \large{9^n} - {2^n} is divisible by \large{7} for all positive integers \large{n}.

a) Show true for n=1.

\large{9^n} - {2^n} = {9^1} - {2^1}

\large = 9 - 2

\large = 7

b) Assume true for n=k.

\large{9^n} - {2^n} becomes \large{9^k} - {2^k}

Write \large{9^k} - {2^k} in equation expressing that it is divisible by \large{7}.

\large{9^k} - {2^k} = 7{\color{blue}x}

for some positive integer \large{x}

Solve for \large\color{red}{9^k}:

\large{\color{red}{9^k}} = 7x + {2^k}

c) Prove the statement is true for n=k+1.

Since y is an integer, thus \large{9^{k + 1}} - {2^{k + 1}} is divisible by 7.

\therefore By the principle of mathematical induction, the statement is true for all positive integers.

You might also be interested in:

Mathematical Induction (Summation)