## anonymous one year ago Please check my solution: Prove that for all integers n > 0, n3 + 2n is divisible by 3.

1. anonymous

Prove that for all integers n > 0, n3 + 2n is divisible by 3. Base Case: n=1 (1)^3+2(1) = 3 3 is divisible by 3 Induction Hypothesis P(K+1) (K+1)^3 + 2(K+1) (K+1)(K+1)(K+1)^3 + 2K+2 K^2+K+K+1 = (3K^2 + 1) + 2K+2 (3K^2 + 1)(K + 1) = (3K^3 + 3K^2) + K+1 = 3K^3 + 3K^2 + K + 1 (3K^3 + 3K^2 + K + 1) + 2K + 2 = 3K^3 + 3K^2 + 3K + 3 3K^3 + 3K^2 + 3K + 3 is divisible by 3 QED

2. zepdrix

I'm kind of getting lost here: (K+1)(K+1)(K+1)^3 + 2K+2 K^2+K+K+1 = (3K^2 + 1) + 2K+2 (3K^2 + 1)(K + 1) = (3K^3 + 3K^2) + K+1 = 3K^3 + 3K^2 + K + 1

3. zepdrix

Use your Binomial Theorem to expand out a cube, $$\large\rm (k+1)^3=k^3+3k^2+3k+3$$ No 3 coefficient on the k^3 term.

4. zepdrix

Woops! +1 on the end, sorry typo

5. zepdrix

$$\large\rm (k+1)^3=k^3+3k^2+3k+1$$

6. zepdrix

Did you do it the other way? Expanding out two brackets at a time?

7. anonymous

Just a moment, let me read over this. It might take me a minute to reply-- I'm not very good at math. Thank you for responding to my question, though.

8. zepdrix

The base case looks good :) We're missing an important step though. The Induction Hypothesis is actually where we assume n=k is true. Then we next apply the Induction Step, which you attempted, we just need to clean a few parts up.

9. anonymous

The induction hypothesis is basically saying "it's true for all integers," right? And, the induction step is where we do K+1 to show it works for the next integer. Is this the correct idea?

10. anonymous

I am going to go over this algebra on a sheet of paper. It may take me 4-5 minutes. If you're lost that means I've done something wrong. Honestly, I haven't done algebra in a long time and I'm kind of fuzzy on my rules. Let me work this out on paper and come to you with concise questions in a few moments.

11. zepdrix

Yes :) We SHOWED that it was true for the very first case. Our hypothesis, our assumption, is that this will be true for any number. If we can show it's true for the number after that, we've showed it's true in general. Ok cool.

12. ganeshie8

Can't resist this alternative proof : $$n^3+2n \\= n^3-n+3n \\= n(n^2-1)+3n \\= (n-1)(n)(n+1)+3n$$ recall the fact that product of any 3 consecutive integers is divisible by 3 to conclude the proof.

13. zepdrix

hah ;) that's clever

14. anonymous

(From Above) (K+1)(K+1)(K+1)^3 + 2K+2 K^2+K+K+1 = (3K^2 + 1) + 2K+2 This was pretty sloppy. I was supposed to have: (K + 1)(K + 1)(K + 1) + 2K+2 Now, I have to multiple whatever I can: (K^2 + K + K + 1)(K + 1) + 2K + 2 Simplify and multiple: (K^2 + 2K + 1)(K + 1) + (2K+2) (K^3 + K^2 + 2K^2 + 2K +K + 1) + (2K+2) (K^3 + 3K^2 + 2K + K + 1) + (2K+2) (K^3 + 3K^2 + 3K + 1) + (2K+2) (K^3 + 3K^2 + 5K + 3) Okay, slightly different answer. I tried to make each step clear; but, my eyes get kind of lost looking at these numbers. Sorry, for my poor work.

15. zepdrix

Ok looks good :) Let's back up a sec though. Stating our Induction Hypothesis: We assume this is true for n=k. Which means $$\large\rm \color{orangered}{k^3+2k}$$ is assumed to be divisible by 3. Hold onto this we'll need it later!

16. zepdrix

In all of your algebra, you actually want to stop here,$\large\rm (k^3 + 3k^2 + 3k + 1) + (2k+2)$And group a little differently than you might think.

17. zepdrix

$\large\rm k^3+2k+3k^2+3k+3$So I arranged them a little differently, hopefully that's not confusing.

18. anonymous

so, you have put your induction hypothesis at the front

19. zepdrix

good good good, we want to see that piece showing up somewhere in our induction step. $\large\rm \color{orangered}{k^3+2k}+3k^2+3k+3$

20. zepdrix

Your next step would be to maybe pull a 3 out of each of these terms. So you can say something about it as a group.$\large\rm \color{orangered}{k^3+2k}+3(k^2+k+1)$

21. zepdrix

We assumed that the orange was divisible by 3. And clearly 3(k^2+k+1) is divisible by 3 (because it's being multiplied by 3). So the whole thing is divisible by 3! :)

22. anonymous

Okay, so for these cases I need to do algebra until I get the induction hypothesis. Move that to one side. Factor out the other side.

23. zepdrix

Yes. Base Case: Prove true for n=1. Induction Hypothesis will give you an equation. Induction Step: Here you are working with a big mess of stuff. You're trying to find the equation from the induction step in it, plus some other stuff.

24. zepdrix

Maybe I'll call it the equation. Induction Hypothesis: the equation. Induction Step: Big Mess = the equation + (stuff that is obviously true)

25. zepdrix

The process isn't too bad :) Just gotta get comfortable with the tons and tons of algebra steps I guess

26. anonymous

Okay, I do have a few more questions if you don't mind. A) When I wrote the base case I entered 1 because that is the first integer greater than 0. Is that the right reason to be using this base case? B) K+1 is part of the induction step. Does this represent the next integer in the sequence of integers being tested (all, in this case).

27. zepdrix

A) Yes. You'll likely later run into problems which state things like prove this is true for for n>3. So you'll have a more awkward starting point of n=4 in that type of problem. But yes, we're only using the counting numbers for n, since these are integers. So n=1 is the next one to go to since it's a strict inequality. If they had given us $$\large\rm n\ge0$$, then we might want to start at n=0, unless it's incredibly trivial to do so. B) Good, yes. We assumed that it would it be true for any number. We showed that if that's true, the number after that is always true as well. So ya, we've covered everything by doing that. If this equation holds for any number greater than 0, then it holds for the next number. Since we showed n=1 is true, then by our induction step, we can say that n=2 must be true. (Because we've shown that the next number is always true). We can continue from that point and say that n=3 must be true. And so on... Hopefully that wasn't too long winded of an explanation lol.

28. anonymous

No, that was great. Thank you very much for taking time out of your day to help me and other people. I genuinely appreciate it. I will continue doing some more problems. If you have time and don't mind, then I will attempt a solution and post it to this chat. Otherwise, have a great day-- and, thanks again! :)

29. zepdrix

cool \c:/

30. zepdrix

ya I'll be around from time to time. You can use the pager system to get someone's attention, it can be useful. @zepdrix would sent me a notification, makes it easier to find this thread again. Or you can @ any of the other smarty pants in the main lobby. Any of the 99 scores are usually pretty helpful.

31. anonymous

@zepdrix in this chat window? I also see there is an option to send private messages. Whichever you prefer. Anyway, next problem in maybe 15-20 min.

32. zepdrix

Yes, in this chat window. It's gives me a notification on the sign post icon. I don't like to answer questions in private message >.< I can't use the fancy equation tool there lol

33. anonymous

@zepdrix prove that for all integers n>0 (8^n)-(3^n) is divisible by 5 Base Case: n=1 (8^1)-(3^1)=5 5/5=1 Induction Hypothesis: n=k Induction Step: (8^k+1)-(5^k+1) I do not know what to do with these exponents. I have been trying to find what to do; but, the information is not coming easy. Could you point me in the right direction or show me what the first operation would be?

34. zepdrix

An exponent rule tells us: $$\large\rm x^{a+b}=x^a\cdot x^b$$ We can apply that to our 8 and 3 bases, $$\large\rm 8^{k+1}=8^k\cdot8^1$$ $$\large\rm 3^{k+1}=3^k\cdot3^1$$ So our expression becomes:$\large\rm 8^{k+1}-3^{k+1}\quad=\quad 8^k\cdot8-3^k\cdot3$From that point.. hmm lemme think about it a sec, it's gonna be a tricky step I think.

35. zepdrix

Recall from your base case that 8-3=5. Manipulate that to get $$\large\rm \color{orangered}{3=(8-5)}$$ I think we'll have to use this in our Induction Step:$\large\rm 8^k\cdot8-3^k\cdot\color{orangered}{3}$

36. zepdrix

Think you can work with that? :) Or still too confusing?

37. anonymous

I am thinking about it. I need to get 8^k-3^k out of this. Is 8^k-3^k = 8-5?? I understand what you are saying by manipulating 3=(8-5). Perhaps it is necessary. I have no idea what I'm doing with this problem.

38. anonymous

@zepdrix I am thinking about it. I need to get 8^k-3^k out of this. Is 8^k-3^k = 8-5?? I understand what you are saying by manipulating 3=(8-5). Perhaps it is necessary. I have no idea what I'm doing with this problem.

39. zepdrix

I colored them orange to show that we're going to make a substitution.

40. zepdrix

So from here,$\large\rm 8^k\cdot8-3^k\cdot\color{orangered}{3}$We'll rewrite 3 as (8-5),$\large\rm 8^k\cdot8-3^k\cdot\color{orangered}{(8-5)}$This algebra step is going to be a little tricky. Distribute the -3^k to each term in the brackets.

41. zepdrix

$\large\rm 8^k\cdot8-3^k\cdot8+3^k\cdot5$Something like that, ya?

42. anonymous

genius.

43. zepdrix

Are you familiar with this notation or no? | that bar? | means "divides" If I say x+y is divisible by 5, another way to say it is, 5 divides x+y Mathematically it looks like this $$\large\rm 5|x+y$$ Have you been introduced to that? :o

44. anonymous

I am familiar, now :P I would have never got this problem. I suppose you can manipulate the base case for the int 8, too.

45. zepdrix

To be honest, I didn't remember how to do this problem either. I had to google it lol. Kind of a weird little step in the middle there.

46. zepdrix

Do you see how to finish that problem up though? :o $\large\rm 8^k\cdot8-3^k\cdot8+3^k\cdot5$From that point?

47. anonymous

8k⋅8−3k⋅(8−5) = 8k * 8 - 24k - 15k No? 8k⋅8−3k⋅8+3k⋅5 <--- How did this happen??

48. zepdrix

Oh boy what happened there +_+ Hmmm

49. zepdrix

It's not 3k, it's 3^k

50. anonymous

(_8^(|) Doh

51. anonymous

ok just a sec

52. anonymous

@zepdrix 8^k⋅8−3^k⋅8+3^k⋅5 from here it's pretty easy to put the induction hypothesis in front. 8^k-3^k*8*8+3^k*5; but, I'm still left with this 3^K which I don't know what to do with. I mean, even if 3^k was set to 0 or 1 that side would be divisible by 5. I'm not sure how to proceed.

53. zepdrix

Woops, the way you got your induction hypothesis looks a little sloppy. Lemme write it out and make sure this makes sense to you,$\large\rm \color{royalblue}{8^k\cdot8-3^k\cdot8}+3^k\cdot5$We're going to factor an 8 out of each blue term,$\large\rm \color{royalblue}{8(8^k-3^k)}+3^k\cdot5$Since our Induction hypothesis tells us that $$\large\rm 5~|~8^k-3^k$$, that implies that $$\large\rm 5~|~8(8^k-3^k)$$ Good, so you can make use of your induction hypothesis to deal with that part.

54. zepdrix

Try to get comfortable with what divisibility means. If I have a number $$\large\rm 2n$$, where n is an integer, then I can confidently say that it's an even number, or in other words, it's a multiple of 2. Which also means it's divisible by 2! (Pssst: Because a 2 is multiplying the number).

55. zepdrix

If I have $$\large\rm 5\cdot stuff$$, I can confidently say that the stuff is a multiple of 5, and is therefore divisible by 5.

56. zepdrix

So as your last step, maybe you just say something like: Since our Induction hypothesis tells us that $$\large\rm 5~|~8^k-3^k$$, this implies that $$\large\rm 5~|~8(8^k-3^k)$$. And further, since $$\large\rm 5~|~5\cdot3^k$$, we have that $$\large\rm 5~|~8(8^k-3^k)+5\cdot3^k$$, proving our induction step.

57. zepdrix

The first chunk is divisible by 5, the second chunk of stuff is divisible by 5, so their sum is divisible by 5.

58. zepdrix

And then wrap it up all fancy at the end with something like: Therefore, by the Principle of Mathematical Induction, $$\large\rm \text{ For all integers }n>0,~~(8^n)-(3^n)\text{ is divisible by }5$$.

59. zepdrix

Unless that seems to wordy :) lol

60. zepdrix

To further nail the point about divisibility though... If something is divisible by 5, it means it can be written as a multiple of 5. Example: $$\large\rm 5~|~x+y$$ means that $$\large\rm x+y=5k$$. Where k is some integer. In our problem: $$\large\rm 5~|~8^k-3^k$$ means that $$\large\rm 8^k-3^k=5\ell$$ where $$\large\rm \ell$$ is some integer. If I multiply both sides by 8,$\large\rm 8(8^k-3^k)=8\cdot5\ell$If we write the right side like this,$\large\rm 8(8^k-3^k)=5\cdot(8\ell)$Do you see how the right side is of the form 5*(stuff)? So it's still divisible by 5! :)

61. zepdrix

Ok that was a lot to chew on :U I'll simmer down

62. anonymous

you're totally fine man. i've been here trying to learn these algebra skills all day. i just forgot about factoring... your explanations are crystal clear and really helpful. simmer as much as you want because I have a test on tuesday :/