Lately I’ve been spending some time investigating the teaching of mathematical induction, and in particular questions which require the proof of a divisibility property. Here’s two:
- Prove that for all integers , is divisible by 57.
- Prove that for all integers , is divisible by 676.
Interestingly enough, for many such problems – and almost all discrete mathematics texts will include, if not these actual problems, then several very similar to them – induction is not necessarily the simplest method of proof.
Let’s look at the first example. I shall give three proofs: two using induction, and one not. For the induction proofs, the base step is trivial: . Now for the inductive step:
- Assume for some . Replace with . Then: by the inductive hypothesis
- We use the fact that for a function if is divisible by 57, and if is dvisible by 57 for some relatively prime to 57, then is divisible by 57.
Here and if we use , then
Now for a proof not using induction, but a tiny bit of number theory. First, write
How simple is that?
Now for the second example. In fact, it is very easy to prove that is divisible by : expand using the binomial theorem, and remove the last two terms; the rest will consist of powers of the lowest of which is . The result follows.
I wonder, of the vast number of induction exercises given to students, how many problems are in fact far more easily proved by other means?