Proof by Induction

Date: 05/24/2002 at 14:01:48
From: David Price
Subject: math induction

Prove by induction that (n^7 - n) is divisible by 42.

Date: 05/24/2002 at 15:56:44
From: Doctor Anthony
Subject: Re: math induction

Let  

  f(n) = n^7 - n

If we prove that f(n) is a multiple of 6 and a multiple of 7, we will
have proved that it is a multiple of 42.

I shall use the notation M(6) to mean 'is a multiple of 6', and M(7)
to mean 'is a multiple of 7'.

   f(n) = n(n^6 - 1)

        = n(n^3 - 1)(n^3 + 1)

        = n(n-1)(n^2+n+1)(n+1)(n^2-n+1)

        = (n-1)n(n+1)(n^2-n+1)(n^2+n+1)

since we have factors (n-1)n(n+1) we have 3 consecutive numbers and 
the product of ANY 3 consecutive numbers will be divisible by 2 and 
also by 3, so therefore also by 6.

The problem reduces to showing that n^7 - n = M(7).  We will do that
by induction:

Show that it is true for a particular value of n, say n=2.  

2^7 - 2  = 126 = 7 x 18 = M(7) 

Assume it is true for some some value n=k, so we assume:

  f(k) = k^7 - k = M(7)    

Now consider the next value  n=k+1

We must show that f(k+1) is also  M(7)

      f(k+1) = (k+1)^7 - (k+1)

             =  k^7 + C(7,1)k^6 + ..... + C(7,6)k + 1 - (k+1)

             = k^7 - k + M(7) + 1 - 1

             = k^7 - k + M(7)

but we have assumed that k^7 - k is divisible by 7  and so the whole 
expression for f(k+1) is divisible by 7.

[Note that all terms of the form C(7,1) to C(7,6) in the working 
shown above will be multiples of 7.]

So if f(k) is M(7) then we have shown that f(k+1) is also M(7).  But 
we have also shown that f(2) is M(7), therefore f(3) is M(7), and if 
f(3) then f(4) and so on to all positive integral values of n.

Therefore n^7 - n is always divisible by both 6 and 7 and therefore 
it is divisible by 42.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/04/2002 at 18:14:50
From: David Price
Subject: math induction

Dear Dr. Anthony

I am a high school math teacher with 25 years experience and I 
could not solve the question using induction.  My two colleagues who
are older than me, one with a math PhD, could not do the question
either. But you and a student of mine did it. Congrats! Dave Price