# How to do Proof by Mathematical 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.

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

Example 1: Prove that is divisible by 2 for all .

The statement of 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.

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 into , we obtain .

Expanding this, we obtain .

Simplifying, this becomes . 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 . Therefore we can substitute with .

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

We can then replace with 2A to obtain .

A factor of 2 can now be taken out of all terms to obtain .

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 .

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 is true (divisible by 2) and is true whenever is true. is true for all .

## 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 is divisible by 3 for all .

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 gives a result of which equals 0.

0 is divisible by 3 since .

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 to obtain .

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

We write .

We can rearrange this for k3 to obtain .

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

Substituting into , we obtain .

Expanding, this becomes .

Collecting like terms, we obtain . It is not obvious that this is divisible by 3.

Therefore we substitute the result from step 2, .

Substituting with , we obtain .

Simplifying this, we obtain and a factor of 3 can now be taken out as .

Therefore the result is divisible 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 is true (divisible by 3) and that is true whenever is true, is true for all .

### Proof by Induction Example: Divisibility by 4

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

Prove that is divisible by 4 for all

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

Substituting n=1, becomes , which equals 8.

8 is divisible by 4 since .

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 , we obtain .

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

We write .

We can rearrange this as .

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

We substitute into to obtain .

We can rewrite as so that becomes .

In step 2, we found that and we can substitute this into the above expression to obtain .

Expanding the brackets this becomes which simplifies to .

We can show that this is divisible by 4 by taking out a factor of 4 as writing the expression as .

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 is true providing is true, must be true for all .

### Proof by Induction Example: Divisibility by 5

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

Prove that is divisible by 5 for all .

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

Substituting n=1 into , we obtain . 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 , we obtain .

We assume this is divisible by 5 and so, we set it equal to 5A to obtain

We can rearrange this as .

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 , we obtain .

This can be written as .

In step 2, we found that .

Therefore can be written as .

Expanding this, we obtain which simplifies to .

Now a factor of 5 can be taken out as to show that it is divisible 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 is true providing is true, must be true for all .

### Proof of Divisibility by 6

Prove that is divisible by 6 for all .

Step 1.

For the base case of n=1, we obtain which is divisible by 6.

Step 2.

Substituting n=k and assuming the result is divisible by 6, we obtain .

We can rearrange this as .

Step 3.

Substituting n=k+1, we obtain .

Expanding this, we obtain .

This simplifies as .

We can use the result from step 2 that to substitute for k3 above.

This becomes which simplifies to .

This is not obvious that it is divisible by 6. We can factorise the last few terms to show this as .

This quadratic can then factorise as .

Now 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 is divisible by 6 because it is 3 multiplied by a multiple of 2.