# Thread: proof by strong induction

1. ## proof by strong induction

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

2. ## Re: proof by strong induction

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

3. ## Re: proof by strong induction

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.

4. ## Re: proof by strong induction

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

5. ## Re: proof by strong induction

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?

6. ## Re: proof by strong induction

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.

7. ## Re: proof by strong induction

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.