How to write proofs by induction about divisibility – video clips

divisibility

There are two video clips here. The first gives one way of doing Step 2 in proofs by induction about divisibility.

Want to prove that m | f(k+1) if m | f(k)? Then “anti-simplify” f(k+1) until you get:

m = something × f(k) + something else divisible by m

I prefer the way in the second clip, where we go the other direction, starting from

m | f(k)

and manipulating that equation until it tells us that

m | f(k+1)

Whichever you prefer.

This is the first way:

And here’s the other way (the better one, I think). This video is a bit longer, because it goes through four different examples.

See also these notes about methods in divisibility proofs.