proof by strong induction

**Jskid** · November 26th 2011, 04:27 PM

My prof is only testing us on the strong form of induction but I can't figure out how to use it with this question.

Use induction to prove $n^3+2n$ is divisible by 3 for n >= 1.

Basis
$n_0 = 1$ then $(1)^3+2(1)=3$ which works
Induction Hypothesis
Let 1<=l<k and assume $l^3+2l$ is divisible by 3
Induction Step
$k^3+2k$
...and now need to use the I.H. somehow

**Also sprach Zarathustra** · November 26th 2011, 04:32 PM

Originally Posted by Jskid

My prof is only testing us on the strong form of induction but I can't figure out how to use it with this question.

Use induction to prove $n^3+2n$ is divisible by 3 for n >= 1.

Basis
$n_0 = 1$ then $(1)^3+2(1)=3$ which works
Induction Hypothesis
Let 1<=l<k and assume $l^3+2l$ is divisible by 3
Induction Step
$k^3+2k$
...and now need to use the I.H. somehow

$(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2={k^3+2k}+3(k^2+k +1)$

**Jskid** · November 26th 2011, 04:37 PM

Originally Posted by Also sprach Zarathustra

$(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2={k^3+2k}+3(k^2+k +1)$

But k+1 is the week form of induction.
Or am I confused? I thought the weak form involves let $n_0 \le l < k$ and you assume the statment is true for l and prove that it is for k.

**Annatala** · November 26th 2011, 10:05 PM

Yes, this is "weak" induction, but you don't need "strong" induction for this problem.

**Jskid** · November 27th 2011, 03:06 PM

Originally Posted by Annatala

Yes, this is "weak" induction, but you don't need "strong" induction for this problem.

Can anyone tell me how this would be solved with strong induction?

**Annatala** · November 27th 2011, 03:15 PM

Originally Posted by Jskid

Can anyone tell me how this would be solved with strong induction?

Do you not realize that strong induction includes weak induction...? The weak induction proof is the strong induction proof, you just don't have to assume as much.

**Deveno** · November 27th 2011, 04:06 PM

strong induction lets you assume the hypothesis for any $1 \leq l < k$ , not just k-1. but, k-1 is indeed < k, so you can use that if you wish.

Thread: proof by strong induction

LinkBack

Thread Tools

Display

proof by strong induction

Re: proof by strong induction

Re: proof by strong induction

Re: proof by strong induction

Re: proof by strong induction

Re: proof by strong induction

Re: proof by strong induction

Similar Math Help Forum Discussions

Strong Induction proof

Proof by strong induction?

Proof Using Strong Induction

Strong Induction proof

Strong induction proof

Search Tags