Proving Divisibility With Induction

We can proved that a closed form for an expression id divisible for a certain number by proving that the difference between sucessive terms is divisible, as well as one of the terms. This is not always as simple as it sounds.

Suppose we are to proveis divisible by 13 .

The standard proof by induction steps involve proving a statement is for an integer, or two, supposing true for an integerthen using these two true statements to prove the statement is true for every subsequent integer.

Suppose thatthenwhich is divisible by 13.

Ifsois divisiblle by 13.

Suppose true u-n

(1)

Now find the remainder on dividing by 13, using also the fact that the remainder of a product is the product of the remainders. (1) becomes

is now a common factor, so

which is obviously divisible by 13.

From (1),

is divisible by 13 by assumption, and we have just shown that the bracketed term is too, sois also divisible by 13 .