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 nge 0, 7^{n+2}+8^{2n+1} is divisible by 57.
  2. Prove that for all integers nge 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}<span class="ql-right-eqno">   </span><span class="ql-left-eqno">   </span><img src="" height="21" width="287" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[latex qquad =7.7^{k+2}+(7+57).8^{2k+1}\]" title="Rendered by"/>latex qquad = 7(7^{k+2}+8^{2k+1})+57.8^{2k+1}

    qquad =7.57N+57.8^{2k+1} by the inductive hypothesisqquad =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

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 (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?

One thought on “Mathematical induction… or not?

Leave a Reply

Your email address will not be published. Required fields are marked *