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

I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs!

Problem:

For any natural number $n , n^3 + 2n$ is divisible by $3.$ This makes sense

Proof:

Basis Step: If $n = 0,$ then $n^3 + 2n = 0^3 +$ $2 \times 0 = 0.$ So it is divisible by $3.$

Induction: Assume that for an arbitrary natural number $n$, $n^3+ 2n$ is divisible by $3.$

Induction Hypothesis: To prove this for $n+1,$ first try to express $( n + 1 )^3 + 2( n + 1 )$ in terms of $n^3 + 2n$ and use the induction hypothesis. Got it

$$( n + 1 )^3+ 2( n + 1 ) = ( n^3 + 3n^2+ 3n + 1 ) + ( 2n + 2 ) \{\text{Just some simplifying}\}$$

$$ = ( n^3 + 2n ) + ( 3n^2+ 3n + 3 ) \{\text{simplifying and regrouping}\}$$ $$ = ( n^3 + 2n ) + 3( n^2 + n + 1 ) \{\text{factored out the 3}\}$$

which is divisible by $3$, because $(n^3 + 2n )$ is divisible by $3$ by the induction hypothesis. What?

Can someone explain that last part? I don't see how you can claim $(n^3+ 2n ) + 3( n^2 + n + 1 )$ 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.