The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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


  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 

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
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.