Proof Through Theory of Induction (Pre-Calc)

[ellist]

The question is to prove through induction that, (n^3) + 2n is divisible by 3. That reads as, n to the power of 3 plus 2n is divisible by three.

Any help is appreciated, my text book does not have a response for this question (save paper maybe). I did get an answer but I do not know if it correct as it includes a variable k in the actual answer. I used the tactic where I proved it is true for 1, then assumed true for k, then tried to prove for k+1.

My answer:

3(k^2+k+1+A)

The A is some integer because (n^3) + 2n = 3A, where 3A is just every multiple of 3.

Hopefully noone is confused and someone has a briliant answer to help me out

 

[stapel]

The question is to prove through induction that, (n^3) + 2n is divisible by 3. That reads as, n to the power of 3 plus 2n is divisible by three....

My answer: 3(k^2+k+1+A)

Has your textbook not covered "proof by induction"? If not, then that would explain why your "answer" is not actually a "proof". To learn how to do induction proofs, try here.

After you have studied at least two lessons from the listing at the link, please attempt the proof. You'll start with the "base" case (being for n = 1). Then you'll assume the generic case (being for n = k, where k is just "any counting number" without any specificity). You'll use the generic case in the induction step (being for n = k + 1).

 

[HallsofIvy]

The question is to prove through induction that, (n^3) + 2n is divisible by 3. That reads as, n to the power of 3 plus 2n is divisible by three.

Any help is appreciated, my text book does not have a response for this question (save paper maybe).

I don't know what "save paper maybe" means. You don't expect you text book to give answers to every problem do you?

I did get an answer but I do not know if it correct as it includes a variable k in the actual answer. I used the tactic where I proved it is true for 1, then assumed true for k, then tried to prove for k+1.

My answer:

3(k^2+k+1+A)

That's part of an answer. Given that \(\displaystyle k^3+ 2k= 3A\), Then \(\displaystyle (k+1)^3+ 2(k+ 1)= k^3+ 3k^2+ 3k+ 1+ 2k+ 2= 3k^2+ 3k+ 3+ (k^3+ 2k)= 3k^2+ 3k+ 3+ 3A= 3(k^2+ k+ 1+ A)\)
That's what you meant, right? Yes, that's correct, you just need to say more.

The A is some integer because (n^3) + 2n = 3A, where 3A is just every multiple of 3.

Hopefully noone is confused and someone has a briliant answer to help me out

 

[ellist]

I don't know what "save paper maybe" means. You don't expect you text book to give answers to every problem do you?


That's part of an answer. Given that \(\displaystyle k^3+ 2k= 3A\), Then \(\displaystyle (k+1)^3+ 2(k+ 1)= k^3+ 3k^2+ 3k+ 1+ 2k+ 2= 3k^2+ 3k+ 3+ (k^3+ 2k)= 3k^2+ 3k+ 3+ 3A= 3(k^2+ k+ 1+ A)\)
That's what you meant, right? Yes, that's correct, you just need to say more.

Actually my text book does give me every single answer except for the problems on induction. The answers are in the back of the text book, but I do find it useful to self correct. I am in the IB system, and my text books for all classes always have answers for every question which I find pretty cool

Thanks for checking my workings, I appreciate it. I just wasn't sure if I had done it correctly because it was the first question where I had a K in my final answer where all my others answers resulted in only constants.

Final note, thanks for the \(\displaystyle tip (saw it in the quote). I was wondering how people made their equations look proper.\)

 

[ellist]

Has your textbook not covered "proof by induction"? If not, then that would explain why your "answer" is not actually a "proof". To learn how to do induction proofs, try here.

After you have studied at least two lessons from the listing at the link, please attempt the proof. You'll start with the "base" case (being for n = 1). Then you'll assume the generic case (being for n = k, where k is just "any counting number" without any specificity). You'll use the generic case in the induction step (being for n = k + 1).

Yes My text has covered proof by induction and I know that my answer given is not a formal proof without all the workings and the final statement of since P1 is true and Pk is true whenever PK + 1is true then all values of n (or k, whichever variable) when N is part of the positive integer set, or something along those lines. I just wanted to know if my expansion of the PK + 1 was correct, and that I hadn't made a silly mistake somewhere along the way and gotten the wrong answer.

 

[stapel]

I know that my answer given is not a formal proof without all the workings and the final statement of since P1 is true and Pk is true whenever PK + 1is true then all values of n (or k, whichever variable) when N is part of the positive integer set, or something along those lines.

No; "the statement is true for n = k + 1 whenever the statement is true for n = k". You've got it backwards. It would probably be a good idea to review at least one lesson geared toward making absolutely clear the actual "sense" of the proof method. :cool:

I just wanted to know if my expansion of the PK + 1 was correct, and that I hadn't made a silly mistake somewhere along the way and gotten the wrong answer.

I'm sorry, but I can't make heads or tails of your "3(k^2+k+1+A) where the A is some integer because (n^3) + 2n = 3A, where 3A is just every multiple of 3." statement. Please reply with your start from "for n = k, we assume that k^3 + 2k is divisible by 3." (Why "k^3 + 2k"? Because we have set n to equal k!)

Please be complete. Thank you!

 

[Dale10101]

Abandoned post?

The question is to prove through induction that, (n^3) + 2n is divisible by 3. That reads as, n to the power of 3 plus 2n is divisible by three.

Any help is appreciated, my text book does not have a response for this question (save paper maybe). I did get an answer but I do not know if it correct as it includes a variable k in the actual answer. I used the tactic where I proved it is true for 1, then assumed true for k, then tried to prove for k+1.

My answer:

3(k^2+k+1+A)

The A is some integer because (n^3) + 2n = 3A, where 3A is just every multiple of 3.

Hopefully noone is confused and someone has a briliant answer to help me out

My thoughts after bouncing off several walls, any correction/comment appreciated.

First: "The A is some integer because (n^3) + 2n = 3A, where 3A is just every multiple of 3"

VECTOR(n³ + 2n, n, 1, 5) = [3, 12, 33, 72, 135] .... so n³ + 2n does not generate every multiple of 3, PREMISE DENIED.

(I think. "premise denied", sounds cool and cruel,no, )

Second: Prove n³ + 2n is divisible by 3 where "n" is an element of the Natural number set "N".

If (n³ + 2n)/3 exists as a natural number then by definition there must be a natural number "A" such that

n³ + 2n = 3A

Assume there is a subset M of N for which A exists as some natural number, that is that t (n³ + 2n) is divisible by 3 for at least some n of N.

Let k be a particular element of M.

If k = 1 then k³+2k = 1³+2(1) = 3 = 3A => A =1, since "1" is a natural number, k = 1 belongs to set M.

Assume k³+2k = 3A is true (i.e. that a natural number A exist for any natural number k), then, does it follow that

(k+1)³+2(k+1) is divisible by 3, that is, that there is some natural number B such that

(k+1)³+2(k+1)= 3B ? so ...

(k+1)³+2(k+1) = k³ + 3k² + 5k + 3 = ( k³ + 2k) + (3k² + 3k + 3) = ( k³ + 2k) + 3(k² + k + 1)

but k³+2k = 3A, so

( k³ + 2k) + 3(k² + k + 1) = ( 3A) + 3(k² + k + 1) = 3(A + (k² + k + 1))

therefore B = (A + (k² + k + 1)) exists as a natural number, it follows then that (k+1)³+2(k+1) is divisible by 3.

Thus we have shown that for k = 1 in particular, and in general for any k of M, if k is an element of M then k+1 is also an element of M, and by the "Axiom of Induction" M contains all natural numbers:

QED, n³ + 2n is divisible by 3 for all natural numbers. (I hope.)

 

[HallsofIvy]

Of course, this can also be done without using induction:

n, like any integer, is a multiple of 3 or one more than a multiple of 3 or two more than a multiple of three.

case 1) n is a multiple of 3. Then n= 3k for some integer k so \(\displaystyle n^3+ 2n= (3k)^3+ 2(3k)= 27k^3+ 6k= 3(9k^3+ 2k)\).

case 2) n is one more than a multiple of 3. Then n= 3k+ 1 for some integer k so \(\displaystyle n^3+ 2n= (3k+1)^3+ 2(3k+1)\)\(\displaystyle = 27k^3+ 27k^2+ 9k+ 1+ 6k+ 2= 27k^3+ 27k^2+ 15k+ 3= 3(9k^3+ 9k^3+ 5k+ 1)\).

case 3) n is two more than a multiple of 3. Then n= 3k+ 2 for some integer k so \(\displaystyle n^3+ 2n= (3k+ 2)^3+ 2(3k+ 2)= 27k^3+ 54k^2+ 36k+ 8+ 6k+ 4\)\(\displaystyle = 27k^3+ 54k^2+ 42k+12= 3(9k^3+ 18k^2+ 14k+ 4)\).

 

[Dale10101]

Yes, pondering ...

Of course, this can also be done without using induction:

n, like any integer, is a multiple of 3 or one more than a multiple of 3 or two more than a multiple of three.

case 1) n is a multiple of 3. Then n= 3k for some integer k so \(\displaystyle n^3+ 2n= (3k)^3+ 2(3k)= 27k^3+ 6k= 3(9k^3+ 2k)\).

case 2) n is one more than a multiple of 3. Then n= 3k+ 1 for some integer k so \(\displaystyle n^3+ 2n= (3k+1)^3+ 2(3k+1)\)\(\displaystyle = 27k^3+ 27k^2+ 9k+ 1+ 6k+ 2= 27k^3+ 27k^2+ 15k+ 3= 3(9k^3+ 9k^3+ 5k+ 1)\).

case 3) n is two more than a multiple of 3. Then n= 3k+ 2 for some integer k so \(\displaystyle n^3+ 2n= (3k+ 2)^3+ 2(3k+ 2)= 27k^3+ 54k^2+ 36k+ 8+ 6k+ 4\)\(\displaystyle = 27k^3+ 54k^2+ 42k+12= 3(9k^3+ 18k^2+ 14k+ 4)\).

I see your point and your method. I am now pondering, privately of course, " Is the method of Induction essential, that is, are there propositions which can be proved no other way?" ... just in case the guy at the intersection is seeking not a dollar but mathematical certainty.

Hmmm, perhaps all of the fundamental operations on the set of natural numbers and integers, addition, multliplication, etc

Third edit, perhaps modern set (Zermelo-Franenkel set theorey et al) is another way of doing all of the same things. Ah ... questions probably vague and pre-mature.