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?

One Response

  1. Possible typo?

    > Here’s two:
    Here are two:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The AIM Network

The Australian Independent Media Network

Follow

Get every new post delivered to your Inbox.

Join 54 other followers

%d bloggers like this: