Proof that $n^3+2n$ is divisible by $3$

In the inductive hypothesis, you assumed that $n^3 + 2n$ was divisible by 3 for some $n$, and now you're proving the same for $n+1$. It's like knocking down dominoes: if you can prove that the first domino falls over (base case) and each domino knocks over the next (inductive step), then that means that all of the dominoes get knocked down eventually.

You know that $(n^3 + 2n) + 3(n^2 + n + 1)$ is divisible by 3 because $n^3 + 2n$ is (because of the inductive hypothesis) and $3(n^2 + n + 1)$ is (because it's 3 times an integer). So, their sum is as well.


Presumably you're only looking for a way to understand the induction problem, but you can note that $n^3+2n = n^3 - n + 3n = (n-1)(n)(n+1) + 3n$. Since any three consecutive integers has a multiple of three, we're adding two multiples of three and so get another multiple of 3.


$$n^3+2n=n(n^2+2)$$

If $n$ is divisible by $3$, then obviously, so is $n^3+2n$ because you can factor out $n$.

If $n$ is not divisible by $3$, it is sufficient to show that $n^2+2$ is divisible by 3. Now, if $n$ is not divisible by $3$, $n=3k+1$ or $n=3k+2$ for some integer $k$. Plug that into $n^2+2$ and you'll get $9k^2+6k+3$ and $9k^2+6k+6$ respectively. Both of which are divisible by 3.