# Homework Help: Proof by Induction

1. Jan 20, 2006

### teng125

anyone pls help........for this ques:For any natural number n, n^3 + 2n is divisible by 3.

i don't know how to start or do

2. Jan 20, 2006

### matt grime

What does induction tell you to do? If you know what induction is then you know how to do this, so start by writing out what you need to do for induction. if you don't understand that then the rest of the question is not important.

3. Jan 20, 2006

### teng125

first to prove that left hand side of the equa is equal to right hand side or the equa which i did it.
then the sec step which is it i should prove that (n+1)^3 + 2(n+1) is also divisible by 3??ah....this step i can't proof

4. Jan 20, 2006

### matt grime

left hand side of what 'equa' is equal to the right hand side of what? Or what is the second 'equa'? (Heck, what was the first).

Show that n^3+2n is divisible by three if n=1 (or zero if you like), now show that if k^3+2k is divisible by three then so is (k+1)^3+2(k+1)

note if X is divisible by three and Y is divisible by three then so is X+Y. So what happens if you subtract k^3+2n from (k+1)^3+2(k+1)?

5. Jan 21, 2006

### HallsofIvy

You titled this "induction". Are you saying you do not know what "proof by induction" means? There are two steps to induction and you certainly should be able to do the first!

Do this: open your text book and look up "proof by induction". Tell us precisely what you need to do to prove "n3+ n is divisible by 3" and we'll help you go from there.

6. Jan 21, 2006

### forevergone

Ok. To do mathematical induction, I was taught to do this in 3 steps. These 3 steps are:

1) Show true for n = 1
2) Assume true for n=k.

By doing this assumption, you set up for the third step by proving true for n=k+1, which will prove that n = k is also true.

3) Prove true for n = k+1.

Follow these steps throughout and see how it goes from there. I'll give you a little head start but try to finish it off.

Step 1: Show true for n=1
$$1^3+2(1) = 3$$ (which is divisable by 3)

Step 2: Assume true for n = k
i.e. Assume $$3 | k^3+2(k)$$ (induction hypothesis)

Step 3: Prove true for n = k+1
i.e. Prove that $$3 | (k+1)^3+2(K+1)$$

Expand out $$(k+1)^3+2(k+1)$$ and when you fully simplify it out, try to keep your induction hypothesis ($$k^3+2(k)$$) separate and see what's left over in your simplified expression. It should result in something that is divisible by 3. Show us how you expand it out and if you make any errors, we'll help you out gladly. But if you dont do the work, we won't help you. It's as simple as that. Effort needs to be shown, not just a problem thats shoved in our faces.

Last edited: Jan 21, 2006
7. Jan 21, 2006

### forevergone

Sorry for double post. This forum really doesn't work well with firefox.

8. Jan 22, 2006