Proving Divisibility With Induction

If we have a sequence defined by an equtation or some recurrence relation, it is natural to be able to prove – if it can be proved at all – that terms are divisible by some number using proof by induction.

The proof is due to the obvious gact that if we can find the difference between the (n+1)th and the nth terms

(this is my own shorthand –is the kth term but in textbooks stands for the statement to be proved).

and then prove thatis divisible by the same number as(by hypothesis) then so isdivisible by the same number.

Example: Prove thatis divisible by 3 for

Letthenso the statement'is divisible by 4' is true.

Now supposeis true so thatis divisible by 3.

Ifis true thenis divisible by 3.

In my own notation,

which is divisible by 3. Sinceis divisible by 3 by hypothesis, so is

Note that we can also writesois the sum of two numbers divisible by 3, somust also be divisible by 3.