Proof by Induction

1. Sep 18, 2004

Parth Dave

I have to prove, using mathematical induction, that:
n^3 - n is divisible by 6.
When n = 1 its true.

Assuming that k^3 - k is divisible by 6

(k+1)^3 - (k+1)
=k^3 + 3k^2 + 2k
= k^3 - k + 3k^2 + 3k
k^3 - k is true by induction hypothesis

but how would i prove that 3k^2 + 3k is divisible by 6? (or did i do this completely wrong?)

Last edited: Sep 18, 2004
2. Sep 18, 2004

Galileo

You're on the right track.
Since 3k^2+3k=3(k^2+k), all you have to show is that k^2+k is divisible by 2.

3. Sep 18, 2004

Parth Dave

How would I do that?

4. Sep 18, 2004

mathwonk

you don't really need induction since factoring it makes it obvious. i.e. (n-1)(n)n+1) is a number that is clearly divisible by both 2 and 3, hence also by 6.

5. Sep 18, 2004

Parth Dave

It has to be done using induction.... and im not sure i see how that is clearly divisible by 2 and 3.

6. Sep 18, 2004

TenaliRaman

(k^2+k) = k(k+1)
if k is odd then (k+1) is even
if k is even then well nothing much left

-- AI

7. Sep 18, 2004

Parth Dave

Ah, ok, thx alot.

8. Sep 18, 2004

mathwonk

every other number is divisible by 2 and every third number is divisible by three so if you have three consecutive numbers then at least one is divisible by two and at least one is divisible by three.

i know you were supposed to do it by induction, but i enjoy puncturing the balloon of the book that gives a question which is artificial, in the sense that it should really be done more naturally or mroe intelligently another way.

drill is ok, but it helps i think if you give an induction proof that really requires induction, or is easier by induction.

for example try proving every integer greater than one is either prime or factors into primes without induction.

Last edited: Sep 18, 2004