Question

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

Answer 1

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

Answer 2

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

Answer 3

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?

Answer 4

no, base case is \(n=1\)

Answer 5

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

Answer 6

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\)

Answer 7

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\)

Answer 8

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

Answer 9

take your time, do the algebra

Answer 10

what is the significance of substituting n for k?

Answer 11

you substitute \(k\) for \(n\) to say what you get to assume is true

Answer 12

not \(n\) for \(k\)

Answer 13

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

Answer 14

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

Answer 15

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\)

Answer 16

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

Answer 17

are you working on the algebra?

Answer 18

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

Answer 19

oh no not \(=3\) no one says it is equal to 3

Answer 20

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

Answer 21

oops i meant
\[(k+1)^3+2(k+1)\]

Answer 22

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

Answer 23

still doing the algebra?

Answer 24

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)

Answer 25

multiply it all out
there is no way around it

Answer 26

do you know how to cube \(k+1\) easily?

Answer 27

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

Answer 28

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

Answer 29

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

Answer 30

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

Answer 31

yeah i got it. sorry about that

Answer 32

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

Answer 33

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

Answer 34

ok you should have \[k^3+3k^2+3k+1+2k+2\]

Answer 35

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

Answer 36

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

Answer 37

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

Answer 38

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

Answer 39

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

Answer 40

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

Answer 41

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

Answer 42

\[\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}}\]

Answer 43

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

Answer 44

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

Answer 45

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

Answer 46

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