# Mathematical Induction

1. Jan 7, 2007

### Bucs44

Here's my problem: 1 * 2 + 2 * 3 + 3 * 4 + . . . + n( n+ 1) = n(n + 1)(n + 2) / 3

3. The attempt at a solution I know that there is a Basis step and Induction step. For the Basis step I have the following but don't know if I'm on the right track: Basis Step 1 * 2 = 1 * 2 * 3 / 3 , which is true

I get lost at the Inductive step.

Any help would be appreciated

Last edited: Jan 7, 2007
2. Jan 7, 2007

### neutrino

Welcome to PF,Bucs.

Which part of the induction step do you have a problem with?

3. Jan 7, 2007

### cristo

Staff Emeritus
Your basis step is right. Where, specifically, do you have problems?

edit: neutrino beat me to it!

4. Jan 7, 2007

### Bucs44

Where I get stuck is what I should be inputing into the statement to verify it.

1*2*3 + n(n+1) = n(n + 1)(n + 2) / 3 +

I'm stuck on how to work the rest of the problem out.

5. Jan 7, 2007

### neutrino

You have to now prove that the above statement holds for n = k+1, assuming that is true for some positive k.

1.2+2.3+...k(k+1) + (k+1)((k+1)+1)

Now, you have to show it takes the form n(n + 1)(n + 2) / 3, for n = k+1.

6. Jan 7, 2007

### Bucs44

I'm not sure that I'm following you - So it would look like this

n(n + 1)(n + 2) / 3 + k(k+1)

n(n + 1)(n + 2) / 3 + k(k+1)/3 / 3

7. Jan 7, 2007

### neutrino

1.2+2.3+...k(k+1) + (k+1)((k+1)+1) ---> This is for k+1

Since we've assumed that it holds true for some arbitrary k greater than 1, we can write

1.2+2.3+...k(k+1) = k(k + 1)(k + 2) / 3 (1)

Now,
1.2+2.3+...k(k+1) + (k+1)((k+1)+1) = k(k + 1)(k + 2) / 3 + (k+1)((k+1)+1) (refer(1))

Simpligy the right-hand side to (k+1)(k+2)(k+3)/3, which is what you would get if you put n = K+1 in n(n + 1)(n + 2) / 3

8. Jan 7, 2007

### Bucs44

Thanks for all of your help neutrino - I think the whole Inductive step is what is really fowling me up - my algebra is poor at best.

9. Jan 7, 2007

### Bucs44

Can I ask you 1 more question though?

2n + 1 < 2n, n = 3, 4 …..
Basis Step (n = 3) - 2(3) = 6 + 1 = 7 < 23 = 8 so we Assume true for n

Am I on the right track?

10. Jan 7, 2007

### neutrino

Are you sure that's the question?

and this whole part...

2(3) = 6 + 1 = 7 < 23 = 8

doesn't make sense.

11. Jan 7, 2007

### Bucs44

I thought by plugging in either 3 or 4 as n that it would be true. I have to verify the inequality

12. Jan 7, 2007

### cristo

Staff Emeritus
This cannot be the correct question, since 2n+1>2n for all n!!

13. Jan 7, 2007

### Bucs44

14. 2n + 1 < 2n, n = 3, 4 …..

It should be less than or equal to - it just didn't come through when I pasted it.

14. Jan 7, 2007

### cristo

Staff Emeritus
Should it not read something like $2n+1\leq 2^n$ for n=3,4,...?

15. Jan 7, 2007

### Bucs44

See - I really am bad at this stuff - the way you have written it is correct.

From my above post I guess my Basis Step is wrong?

Last edited: Jan 7, 2007
16. Jan 7, 2007

### cristo

Staff Emeritus
Well, your basis step: It is true for n=3 so assume true for n=k by the inductive hypothesis. So, we know that $2n+1\leq 2^n$, for n=3,...,k, and we want to show true for n=k+1. So, we have $2(k+1)+1=2k+2+1$. Can you invoke the fact that we know is true (i.e. it holds for n=k) into this equation?

17. Jan 7, 2007

### HallsofIvy

Staff Emeritus
If you think that 2n, when n= 3, equals 23, this may be hopeless. Do you know what "2n" means?

18. Jan 7, 2007

### Bucs44

I'm not sure what you mean by "it holds for n=k"

19. Jan 7, 2007

### cristo

Staff Emeritus
You have proven by your inductive hypthesis that $2k+1\leq 2^k$

20. Jan 7, 2007

### Bucs44

That's all that's to that problem? I thought it would be much more difficult than that.