# Proof by Induction: Divisibility

Let's look at an example of Proof by Induction with 'divisibility'^{[1]}.

## Example

We want to prove that .

As usual with proof by induction, we'll need:

- a base case
- an induction step
- a conclusion

## Divisibility Notation

We are considering the statement: " is divisible by 60".

Since the statement is given in words, "... is divisible by 60", I would prefer to reflect the same use of language, and I'll talk about divisibility using the same words.

There is notation for divisibility that can be used instead. You would say:

The pipe symbol, a perfectly vertical line, is representing the idea of divisibility here. You can read out loud as the word "divides", and say "60 divides ".

All of these statements are equivalent ways of saying the same thing, remembering that we are talking here about integers:

- 60 divides ,
- 60 is a factor of ,
- 60 is a divisor
^{[2]}of , - 60 goes into perfectly,
- is divisible by 60,
- is a multiple of 60,
- is in the 60-times table,
- .

When we say , you might expect that . You can imagine that the times table goes , and must be one of these. But, be careful about this, since it is not exactly true: is in the 60-times table, and so is and so on.

When trying to prove that something is divisible by 60, it can be nice to take out a factor of 60, explicitly showing that every term (as you have written it) is divisible by 60.

## Proof by Induction

#### Base Case

Note! The proof asks us to start with .

In fact, the statement is not true for , so we can't have a base case of : our whole proof will collapse, like the bottom of a house of cards. We have to start our base case with , and then our proof will build from there.

Consider .

This proves that is true for the "base case" of .

When writing this out for an examiner, you'll notice that:

- I have explicitly taken out a factor of 60, and,
- I wrote "which is divisible by 60", reflecting the language of the question and completing the statement in the same way as .

#### Induction Step

In this step, we forget about and focus on the general idea: if we know the statement is true for one integer, can we prove it's true for the next integer.

##### Induction Step: Assumption

We always start the induction step with an assumption: that the statement is true for a particular value, .

So, here, we assume that . In other words:

We expect to use this assumption in the "meat" below, but we may not see it immediately - we may have to "force" the algebra, or un-simplify it, to be able to use the assumption.

##### Induction Step: Goal

We now want to show that the statement is true for , whenever our assumption is true.

So, we want to show that .

As usual, I like to write the goal in a cloud to the side of my work, and treating it as a "show that" question. I must be careful to not use the goal in my work - or this creates circular logic.

I want to start with the statement on the first line, and end on the last line saying "which is divisible by 60".

##### Induction Step: "The Meat"

I have to start with, and I want to force to appear out of it, so I can use then the assumption seen above at .

Since the first term is shown to be divisible by 60, and our assumption says that is divisible by 60, the whole thing is divisible by 60. QED^{[3]}.

Note: this only proves the induction step. We still need to have an overall conclusion.

#### Conclusion(s)

As in all Proofs by Induction, we need our three lines of conclusion:

- The statement is true for
**.** **If**the statement is true for ,**then**it is true for .- Therefore, the statement is true for all n such that .

## Alternative using Function Notation

With a bit of extra set-up, and function notation, we can reduce the amount of writing. Here is the same proof again, with the setup carefully defining the function :

Let .

##### Alternative: Base Case

So, is divisible by 60.

##### Alternative: Induction Step

Assume that f(k) is divisible by 60. Then:

Therefore, **if** f(k) is divisible by 60, **then** f(k+1) is also divisible by 60^{[4]}.

##### Alternative: Conclusion

We still need three points of conclusion, but we have written two of them clearly already.

Therefore, f(n) is divisible by 60 for .

## More Proofs by Induction

Proof by Induction is a very powerful tool and "the meat" can look slightly different in different contexts. It's worth it to look at further examples:

- Proof by Induction
- Proof by Induction: Divisibility
- Proof by Induction: Recursion
- Proof by Induction: Matrices
- Proof by Induction: Inequalities
- Proof by Induction: "Strong" Induction

## Footnotes

- β Divisibility proofs can typically also be done without induction, but A-Level examiners may ask you to do this with induction.
- β chiefly American, I think.
- β Latin for "quod erat demonstrandum", i.e. "that which was to be demonstrated". We have done what we planned to do, according to our goal. There are other ways of notating this including a small square .
- β You may notice that we can also say the same about 120. However, we shouldn't, because this isn't what we are trying to prove. The base case does not support this, so our proof would have no foundation.