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:

Prove that for all integers $n\ge 0$ , $7^{n+2}+8^{2n+1}$ is divisible by 57.
Prove that for all integers $n\ge 1$ , $27^n-26n-1$ 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: $7^2+8=57$ . Now for the inductive step:

Assume $7^{k+2}+8^{2k+1}=57N$ for some $N$ . Replace $k$ with $k+1$ . Then: $7^{k+3}+8^{2k+3}=7.7^{k+2}+64.8^{2k+1}$ $\qquad =7.7^{k+2}+(7+57).8^{2k+1}$ $\qquad = 7(7^{k+2}+8^{2k+1})+57.8^{2k+1}$ $\qquad =7.57N+57.8^{2k+1}$ by the inductive hypothesis $\qquad =57(7N+8^{2k+1})$
We use the fact that for a function $f(n)$ if $f(k)$ is divisible by 57, and if $f(k+1)-rf(k)$ is dvisible by 57 for some $r$ relatively prime to 57, then $f(k+1)$ is divisible by 57.
Here $f(n)=7^{n+2}+8^{2n+1}$ and if we use $r=7$ , then
$f(k+1)-7f(k)=57.8^{2k+1}$ .

Now for a proof not using induction, but a tiny bit of number theory. First, write

$7^{n+2}+8^{2n+1}=49.7^n+8.64^n$ .

Then:

$49.7^n+8.64^n=49.7^n+8.7^n\mod{57}$

$=57.7^n\mod{57}$

$=0\mod{57}.$

How simple is that?

Now for the second example. In fact, it is very easy to prove that $(a+1)^n-an-1$ is divisible by $a^2$ : expand $(a+1)^n$ using the binomial theorem, and remove the last two terms; the rest will consist of powers of $a$ the lowest of which is $a^2$ . The result follows.