How to do Proof by Mathematical Induction for Divisibility

Video Lesson: Proof by Induction for Divisibility

How to Prove Divisibility using Proof by Induction

To prove divisibility by induction, follow these steps:

  1. Show that the base case (where n=1) is divisible by the given value.
  2. Assume that the case of n=k is divisible by the given value.
  3. Use this assumption to prove that the case where n=k+1 is divisible by the given value.
  4. Conclude that by induction, the divisibility is true for all values of n.
steps of proof by induction

We will now look at these four steps in more detail with a few examples of proof by induction.

Example 1: Prove that f of n equals n squared plus n is divisible by 2 for all n is a. member of the positive integers.

The statement of n is a. member of the positive integers means that only positive integer values of n will be considered in this proof.

Step 1. Show that the base case (where n=1) is divisible by the given value

For the set of positive integers, the first positive integer is 1.

Therefore the base case is when n = 1.

We substitute n = 1 into n2 + n to obtain 12 + 1 = 2.

This result of 2 is divisible by 2 and therefore the base case is divisible by 2.

Step 2. Assume that the case of n=k is divisible by the given value

The result when n = k is assumed to be divisible by 2.

That is, when we substitute n = k into the expression, it is assumed that the result is divisible by 2.

Substituting n = k, we obtain k2 + k and we set this equal to 2A to show that it it divisible by 2. This is because any value that is divisible by 2 is equal to 2 multiplied by some other number. We can write this as 2A.

Therefore we write k2 + k = 2A.

proof by induction divisibility by 2 step 1
Step 1. Show that the base case is divisible by 2
proof by induction of divisibility by 2 step 2
Step 2. Assume that the case of n = k is divisible by 2

Step 3. Use this assumption to prove that the case where n=k+1 is divisible by the given value

This is the inductive step in which most of the algebra is conducted.

The goal is to substitute n = k+1 and show that the result can be simplified to an expression that is divisible by 2.

Substituting n equals k plus 1 into n squared plus n, we obtain open paren k plus 1 close paren squared plus open paren k plus 1 close paren.

Expanding this, we obtain k squared plus 2 k plus 1 plus k plus 1.

Simplifying, this becomes k squared plus 3 k plus 2. However, it is not clear that this is divisible by 2.

Now this is fully simplified, we need to use the assumption from step 2 to assist with proving that it is divisible by 2.

In step 2 we found that k squared plus k equals 2 A. Therefore we can substitute k squared plus k with 2 A.

We split the 3k term into k + 2k and this creates k squared plus k plus 2 k plus 2.

We can then replace k squared plus k with 2A to obtain 2 A plus 2 k plus 2.

A factor of 2 can now be taken out of all terms to obtain 2 times open paren A plus k plus 1 close paren.

proof by induction divisibility step 3
proof by induction of divisibility by 2 step 4

Step 4. Conclude that by induction, the divisibility is true for all values of n

When n=k+1 is substituted, the result can be written as 2 times open paren A plus k plus 1 close paren.

Therefore it can be concluded that the result for n=k+1 is divisible by 2 provided that the result for n=k is divisible by 2.

This means that if one particular value of n is divisible by 2, then the following value of n will also be divisible by 2.

Since we showed the base case of n=1 gave us a result that was divisible by 2, all following values of n must therefore give us a result that is divisible by 2.

We can state that since f of 1 is true (divisible by 2) and f of open paren k plus 1 close paren is true whenever f of k is true. f of n is true for all n is a. member of the positive integers.

proof by induction for divisibility by 2

Examples of Proof by Induction for Divisibility

Here are some further examples of using proof by induction to prove divisibility.

Proof by Induction Example: Divisibility by 3

Here is an example of using proof by induction to show divisibility by 3.

Prove that f of n equals n cubed minus n is divisible by 3 for all n is a. member of the positive integers.

Step 1. Show that the base case (where n=1) is divisible by the given value

The base case is when n=1.

Substituting n=1 into n cubed minus n gives a result of 1 cubed minus 1 which equals 0.

0 is divisible by 3 since 0 divided by 3 equals 0.

Therefore the base case of n=1 provides a result that is divisible by 3.

Step 2. Assume that the case of n=k is divisible by the given value
We substitute n=k into n cubed minus n to obtain k cubed minus k.

We set this equal to 3A to show that it is assumed to be divisible by 3.

We write k cubed minus k equals 3 A.

We can rearrange this for k3 to obtain k cubed equals 3 A plus k.

step 1 of proof by induction divisibility by 3
step 2 of proof by induction divisibility by 3

Step 3. Use this assumption to prove that the case where n=k+1 is divisible by the given value

Substituting n equals k plus 1 into n cubed minus n, we obtain open paren k plus 1 close paren cubed minus open paren k plus 1 close paren.

Expanding, this becomes k cubed plus 3 k squared plus 3 k plus 1 minus k minus 1.

Collecting like terms, we obtain k cubed plus 3 k squared plus 2 k. It is not obvious that this is divisible by 3.

Therefore we substitute the result from step 2, k cubed equals 3 A plus k.

Substituting k cubed with 3 A plus k, we obtain 3 A plus k plus 3 k squared plus 2 k.

Simplifying this, we obtain 3 A plus 3 k squared plus 3 k and a factor of 3 can now be taken out as 3 times open paren A plus k squared plus k close paren.

Therefore the result is divisible by 3.

step 3 of proof by induction divisibility by 3
step 4 of proof by induction divisibility by 3

Step 4. Conclude that by induction, the divisibility is true for all values of n

Since the base case of n=1 was divisible by 3 and the n=k+1 case is divisible by 3 provided that the n=k case is divisible by 3, the proof is complete.

We state that since f of 1 is true (divisible by 3) and that f of open paren k plus 1 close paren is true whenever f of k is true, f of n is true for all n is a. member of the positive integers.

proof by induction example of divisibility by 3

Proof by Induction Example: Divisibility by 4

Here is an example of using proof by induction to prove divisibility by 4.

Prove that f of n equals 5 to the power of n plus 3 is divisible by 4 for all n is a. member of the positive integers

Step 1. Show that the base case (where n=1) is divisible by the given value

Substituting n=1, 5 to the power of n plus 3 becomes 5 to the first power plus 3, which equals 8.

8 is divisible by 4 since 8 divided by 4 equals 2.

The base case is divisible by 4.

Step 2. Assume that the case of n=k is divisible by the given value

Substituting n=k into 5 to the power of n plus 3, we obtain 5 to the power of k plus 3.

We set this equal to 4A as we assume that it is divisible by 4.

We write 5 to the power of k plus 3 equals 4 A.

We can rearrange this as 5 to the power of k equals 4 A minus 3.

step 1 of proof by induction divisibility by 4

Step 3. Use this assumption to prove that the case where n=k+1 is divisible by the given value

We substitute n equals k plus 1 into 5 to the power of n plus 3 to obtain 5 raised to the k plus 1 power plus 3.

We can rewrite 5 raised to the k plus 1 power as 5 times 5 to the power of k so that 5 raised to the k plus 1 power plus 3 becomes 5 times 5 to the power of k plus 3.

In step 2, we found that 5 to the power of k equals 4 A minus 3 and we can substitute this into the above expression to obtain 5 times open paren 4 A minus 3 close paren plus 3.

Expanding the brackets this becomes 20 A minus 15 plus 3 which simplifies to 20 A minus 12.

We can show that this is divisible by 4 by taking out a factor of 4 as writing the expression as 4 times open paren 5 A minus 3 close paren.

step 3 of proof by induction divisibility by 4
step 4 of proof by induction divisibility by 4

Step 4. Conclude that by induction, the divisibility is true for all values of n

Since the base case of n=1 is true and f of open paren k plus 1 close paren is true providing f of k is true, f of n must be true for all n is a. member of the positive integers.

proof by induction divisibility by 4

Proof by Induction Example: Divisibility by 5

Here is an example of using proof by induction to prove divisibility by 5.

Prove that f of n equals 8 to the power of n minus 3 to the power of n is divisible by 5 for all n is a. member of the positive integers.

Step 1. Show that the base case (where n=1) is divisible by the given value

Substituting n=1 into 8 to the power of n minus 3 to the power of n, we obtain 8 to the first power minus 3 to the first power equals 5. This result is divisible by 5 and so, the base case where n=1 is divisible by 5.

Step 2. Assume that the case of n=k is divisible by the given value

We assume that the case of n=k is divisible by 5.

Substituting n=k into 8 to the power of n minus 3 to the power of n, we obtain 8 to the power of k minus 3 to the power of k.

We assume this is divisible by 5 and so, we set it equal to 5A to obtain 8 to the power of k minus 3 to the power of k equals 5 A

We can rearrange this as 8 to the power of k equals 5 A plus 3 to the power of k.

step 1 of proof by induction divisibility by 5
step 2 of proof by induction divisibility by 5

Step 3. Use this assumption to prove that the case where n=k+1 is divisible by the given value

Substituting n=k+1 into 8 to the power of n minus 3 to the power of n, we obtain 8 raised to the k plus 1 power minus 3 raised to the k plus 1 power.

This can be written as 8 times open paren 8 to the power of k close paren minus 3 times open paren 3 to the power of k close paren.

In step 2, we found that 8 to the power of k equals 5 A plus 3 to the power of k.

Therefore 8 times open paren 8 to the power of k close paren minus 3 times open paren 3 to the power of k close paren can be written as 8 times open paren 5 A plus 3 to the power of k close paren minus 3 times open paren 3 to the power of k close paren.

Expanding this, we obtain 40 A plus 8 times open paren 3 to the power of k close paren minus 3 times open paren 3 to the power of k close paren which simplifies to 40 A plus 5 times open paren 3 to the power of k close paren.

Now a factor of 5 can be taken out as 5 times open paren 8 A plus 3 to the power of k close paren to show that it is divisible by 5.

step 3 of proof by induction divisibility by 5
step 4 of proof by induction divisibility by 5

Step 4. Conclude that by induction, the divisibility is true for all values of n

Since the base case of n=1 is true and f of open paren k plus 1 close paren is true providing f of k is true, f of n must be true for all n is a. member of the positive integers.

proof by induction divisibility by 5

Proof of Divisibility by 6

Prove that f of n equals n cubed plus 3 n squared plus 2 n is divisible by 6 for all n is a. member of the positive integers.

Step 1.

For the base case of n=1, we obtain 1 cubed plus 3 times 1 squared plus 2 times 1 equals 6 which is divisible by 6.

Step 2.

Substituting n=k and assuming the result is divisible by 6, we obtain k cubed plus 3 k squared plus 2 k equals 6 A.

We can rearrange this as k cubed equals 6 A minus 3 k squared minus 2 k.

Step 3.

Substituting n=k+1, we obtain open paren k plus 1 close paren cubed plus 3 times open paren k plus 1 close paren squared plus 2 times open paren k plus 1 close paren.

Expanding this, we obtain k cubed plus 3 k squared plus 3 k plus 1 plus 3 k squared plus 6 k plus 3 plus 2 k plus 2.

This simplifies as k cubed plus 6 k squared plus 11 k plus 6.

We can use the result from step 2 that k cubed equals 6 A minus 3 k squared minus 2 k to substitute for k3 above.

This becomes 6 A minus 3 k squared minus 2 k plus 6 k squared plus 11 k plus 6 which simplifies to 6 A plus 3 k squared plus 9 k plus 6.

This is not obvious that it is divisible by 6. We can factorise the last few terms to show this as 6 A plus 3 times open paren k squared plus 3 k plus 2 close paren.

This quadratic can then factorise as 6 A plus 3 times open paren k plus 1 close paren times open paren k plus 2 close paren.

Now open paren k plus 1 close paren times open paren k plus 2 close paren will always be the product of two consecutive numbers and therefore must be even. This is because one of the numbers must be a multiple of 2.

Therefore 3 times open paren k plus 1 close paren times open paren k plus 2 close paren is divisible by 6 because it is 3 multiplied by a multiple of 2.

how to prove that n^3+3n^2+2n is divisible by 6