# 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 $n\ge 0$, $7^{n+2}+8^{2n+1}$ is divisible by 57.
2. 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.

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?