# Mathematical induction… or not?

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:

1. Prove that for all integers , is divisible by 57.
2. 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?

## One thought on “Mathematical induction… or not?”

1. mvngu says:

Possible typo?

> Here’s two:
Here are two: