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

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
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search