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

.

Then:

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?

Possible typo?

> Here’s two:

Here are two: