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 that
is divisible by the same number as
(by hypothesis) then so is
divisible by the same number.
Example: Prove that
is divisible by 3 for
Let
then
so the statement
'
is divisible by 4' is true.
Now supposeis true so thatis divisible by 3.
Ifis true then
is 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 write
sois the sum of two numbers divisible by 3, somust also be divisible by 3.
