# Mathematical Induction Help Needed

1. Nov 30, 2005

### GeoMike

The following problem is given in my algebra book:
For all positive integers n, n(n+1)(n+2) is divisible by 6. Prove using mathematical induction.

First:
k=1, 1(1+1)(1+2) = 1(2)(3) = 6, which is obviously divisible by 6

Next:
k(k+1)(k+2)

And then:
(k+1)(k+2)(k+3)

From this I distributed the (k+3) to get:
k(k+1)(k+2) + 3(k+1)(k+2)

The first term is the assumed case (k, divisible by 6)
But 3(k+1)(k+2) doesn't appear to be a clear case of being divisible by 6.

So... I multiplied it out:
$$3(k+1)(k+2) = 3(k^2+3k+2) = 3k^2+9k+6$$

From here I took $$3k^2+9k+6$$ and restarted the process, so:
For k=1, $$3(1)^2+9(1)+6 = 3+9+6 = 18$$, which is divisible by 6

The k case:
$$3k^2+9k+6$$

And the k+1 case:
$$3(k+1)^2+9(k+1)+6 = 3(k^2+2k+1)+9k+9+6 = 3k^2+6k+3+9k+9+6$$

Collecting terms:
$$(3k^2+9k+6) + (6k+12)$$, The first part being the assumed case (k), and the second part is obviously divisible by 6

So I worked it and was able to prove it (I think, unless I did something wrong). What I want to know is: is there an easier way to do this (using just the basic mathematical induction that the book wants)? It seems like I took more steps than necessary/over-complicated the proof. Could I have made it more concise? Is it ok as is?

Thanks!
GM

Last edited: Nov 30, 2005
2. Nov 30, 2005

### Tide

Do you need to use induction? You could simply observe that at least one of the three consecutive integers is even and at least one is multiple of 3.

3. Nov 30, 2005

### HallsofIvy

Staff Emeritus
As Tide pointed out, of three consecutive integers, at least one must be even and one must be a multiple of 3.

If you are required to use induction, then when you have
k(k+1)(k+2) + 3(k+1)(k+2) you can note that k(k+1)(k+2) is a multiple of 6 by the induction hypothesis and that one of the two consecutive integers k+1 and k+2 must be even so 3(k+1)(k+2) must be a multiple of 6 also. If you want to do that more formally, do it as two cases: if k is even- k= 2m, then k+ 2= 2m+ 2= 2(m+1) so 3(k+1)(k+2)= 6(2m+1)(m+1).
If k is odd- k= 2m+ 1 then k+ 1= 2m+ 1+ 1= 2m+ 2= 2(m+1) so 3(k+1)(k+2)= 6(m+1)(2m+3).

4. Nov 30, 2005

### GeoMike

Thanks to both of you!
Yes, the section in the book is on mathematical induction and the exercises explicitly ask that I use mathematical induction.

Like you both pointed out, some of them are quite obvious as stated (#23 in the book is "x>1, prove $$x^n > 1$$ for all natural numbers n")

What is really holding me up are the examples where there are no straightforward ways to proceed (that I can see anyway).
Like with one example in the exercise set:

Prove that $$3^n-1$$ is divisible by 2 for all natural numbers n, use mathematical induction. I couldn't figure out what to do after the basic n=1, k, and k+1 part. I didn't come up with an answer.

In the back of the book they prove it by adding 0 (in the form of $$3^k - 3^k$$) to $$3^{k+1}-1$$. The worked out example in the back of the book made perfect sense to me, but I never would have thought to do it that way on my own. There are a few others in the book that have solutions involving steps that seem to "come out of the blue". All of the steps involve really basic algebraic concepts (like adding 0 to an equation using a number and its additive inverse as with the above problem) but there doesn't seem to be any clear indication of when to use what basic concepts and where. Is that knowledge something that comes with time and practice? Or am I dense? :tongue2:

Thanks again,
GM

Last edited: Nov 30, 2005