## Video Lesson: Proof by Induction for Divisibility

## How to Prove Divisibility using Proof by Induction

**To prove divisibility by induction, follow these steps:**

- Show that the base case (where n=1) is divisible by the given value.
- Assume that the case of n=k is divisible by the given value.
- Use this assumption to prove that the case where n=k+1 is divisible by the given value.
- 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 n^{2} + n to obtain 1^{2} + 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 k^{2} + 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 k^{2} + 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 k^{3} 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 k^{3} 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.