## anonymous one year ago using induction, prove that for all integers n > 0, n3 + 2n is divisible by 3. please help.

1. anonymous

first of all maybe we can see why it is true without induction

2. anonymous

or just do it by induction either way have you ever done a proof by induction?

3. anonymous

i'm supposed to solve it using induction. it's obvious that it's true. even if i plug in 0 it works. but, i don't understand understand how to set this up. i know i need a base case. would that be n=0?

4. anonymous

no, base case is $$n=1$$

5. anonymous

in which case you get 3, so done with the base case

6. anonymous

next you assume it is true if $$n=k$$ in other words you say "we assume $$k^3+2k$$ is divisible by $$3$$" and using that, prove it is true if $$n=k+1$$

7. anonymous

most of it now is algebra from here on in replace $$n$$ by $$k+1$$ and separate out a part of the result that looks like $$k^3+2k$$ and the rest will be obviously divisible by $$3$$

8. anonymous

one sec let me try to absorb what you said. thank you for helping me. i will reply in a min with questions

9. anonymous

take your time, do the algebra

10. anonymous

what is the significance of substituting n for k?

11. anonymous

you substitute $$k$$ for $$n$$ to say what you get to assume is true

12. anonymous

not $$n$$ for $$k$$

13. anonymous

ok, so by saying k we are just saying we assume it's true. this signifies induction?

14. anonymous

and if k+1 is true then the proof is complete?

15. anonymous

yes that is the "induction hypothesis" assume it is true if $$n=k$$ then you use that to prove it is true if $$n=k+1$$

16. anonymous

some people cheat and assume it is true for $$n$$ then show it is true for $$n+1$$ but really we should change the variable

17. anonymous

are you working on the algebra?

18. anonymous

i am trying to work on the algebra. this is what i have to solve: (k+1)^3+2(k+1)=3

19. anonymous

oh no not $$=3$$ no one says it is equal to 3

20. anonymous

just take $(k+1)^2+2(k+1)$ and expand it, then take out the part that looks like $$k^3+2k$$ and separate it from the rest

21. anonymous

oops i meant $(k+1)^3+2(k+1)$

22. anonymous

go ahead and expand it, let me know what you get

23. anonymous

still doing the algebra?

24. anonymous

i am.. i feel retarded. thanks again for helping :\ i am trying to figure out what else i do after (k+1)((k+1)^2)+2(k+1)

25. anonymous

multiply it all out there is no way around it

26. anonymous

do you know how to cube $$k+1$$ easily?

27. anonymous

in general $(a+b)^3=a^2+3a^2b+3ab^2+b^2$ in your case $$a=k,, b=1$$

28. anonymous

and of course $$2(k+1)=2k+2$$

29. anonymous

okay. i have to do (k+1)(k+1)(k+1) and multiply all of it.

30. anonymous

yes, but i showed you how to do it in one step

31. anonymous

yeah i got it. sorry about that

32. anonymous

take your time, let me know what you get when you do all this algebra then we will be done in two steps after

33. anonymous

what did you mean by separate it from the rest? it's all multiplied out. k^2+3k^2(1)+3k(1)^2+1^2 + 2k+1 but there is no right side

34. anonymous

ok you should have $k^3+3k^2+3k+1+2k+2$

35. anonymous

you forgot to distribute with $$2(k+1)$$ i think

36. anonymous

and also you wrote $$1^2$$ but i am sure you didn't mean to

37. anonymous

now only two steps separate out the $$k^3+2k$$ part, that we get to assume is divisible by 3

38. anonymous

you have $\color{blue}{k^3+2k}+\color{red}{3k^2+3k+3}$

39. anonymous

the blue part is divisible by 3 "by induction" we got to assume that the red part is divisible by 3 because... well because it is you can factor a 3 out of it if you want to be formal

40. anonymous

if the red wasn't divisible would it not be a proof?

41. anonymous

yeah you need that part to be divisible by 3 the blue part is the induction hypotheses the red part is what you have to show is divisible by 3, but there is not much to show since each term has a 3 in it

42. anonymous

$\color{blue}{k^3+2k}+\color{red}{3k^2+3k+3}$ $\overbrace{\color{blue}{k^3+2k}}^{\text{ div by 3 by induction}}+\overbrace{\color{red}{3(k^2+k+1)}}^{\text{ has a factor of 3}}$

43. anonymous

and now we are done hope this helped clarify how to do a proof by induction they all pretty much work this way

44. anonymous

i can't believe i found someone to walk me through that

45. anonymous

yeah it is usually a thankless task because most people have no idea about what it means so you have to explain every step of the way, and they get frustrated really it is something you have to see done a few times to understand the logic glad it helped

46. anonymous

if i can find out how to donate to you i will :)