# REAL ANALYSIS, Mathematical Induction

1. Aug 29, 2010

### phillyolly

1. The problem statement, all variables and given/known data

What is wrong with my solution?...
I don't quite understand where do I go from there...

2. Relevant equations

3. The attempt at a solution

#### Attached Files:

• ###### pic.jpg
File size:
15.5 KB
Views:
120
Last edited: Aug 29, 2010
2. Aug 29, 2010

$$k^3 + 3k^2 + 8k + 6 = (k^3 + 5k) + 3k^2 + 3k + 6.$$

$$= (k^3 + 5k) + 3(k^2 + k + 2).$$

From our induction hypothesis, we know the first term is divisible by 6. So it remains to show that $$k^2 + k + 2$$ is divisible by 2 for all k. It's a mini-induction proof within your main induction proof. Can you finish up?

3. Aug 29, 2010

### phillyolly

Yay! You are here!!
Let me see....

4. Aug 29, 2010

### phillyolly

I have no idea what you are talking about.

5. Aug 29, 2010

### jgens

No need for another proof by induction. Just note that k2+k+2 = k(k+1)+2 and the proof follows immediately.

6. Aug 29, 2010

### phillyolly

This is all I understand.
I am sorry, I need one more hint.

#### Attached Files:

• ###### pic.jpg
File size:
17 KB
Views:
99
7. Aug 29, 2010

Oops, I totally overlooked that.

8. Aug 29, 2010

phillyolly, you have (k^3 + 5k) + 3(k(k+1) + 2). We want to show this is divisible by 6, right? Well we already know (k^3 + 5k) is divisible by 6 because we assumed so in our induction proof. So now we just have to prove 3(k(k+1) + 2) is divisible by 6=3*2, i.e., prove it's divisible by 3 AND 2.

Clearly it's divisible by 3 already. So we just have to show k(k+1) + 2 is divisible by 2. Well clearly the right term is divisible by 2. So we just need to show k(k+1) is divisible by 2. Well, if k is even, then this is clearly true. If k is odd, then the factor of (k + 1) is even, so k(k+1) is still divisible by 2. Thus, 3(k(k+1) + 2) is divisible by 6. Do you follow?

9. Aug 29, 2010

Okay, you're fine you have to use the inductive hypothesis combined with a brief observation. You assumed that $$6 | (n^3+5n)$$ for all n. So you then consider the case $$(n+1)^3 + 5(n+1)$$ which you have shown equals $$(n^3+5n) + (3n^2+3n+6)$$. Looking at the left terms you can use your inductive hypothesis. Thus you must show that 6 divides $$3n^2+3n+6$$, and then you can use the property that if "a divides b" and "a divides c" then "a divides b+c" to finish the proof.
Now to show 6 divides $$3n^2+3n+6$$, you will use another theorem. If "n divides a" and "m divides b" then "nm divides ab". Clearly 3 divides $$3n^2+3n+6 = 3 (n^2 + n +2)$$. Now if you can show that 2 divides $$n^2 + n + 2$$, then the second sentence of this paragraph tells you that you're done. Well, why is this? The easiest way to do this is to recognize that there are two possibilities for n: n is even or odd. If n is odd n=2k+1, if n is even n = 2k. Now, work out the details for both cases. More importantly, when you're done, put all the pieces back together to make a nice story.