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