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

Question

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³ + 2n is divisible by 3. This makes sense

Proof:

Basis Step: If n = 0, then n³ + 2n = 0³ + 2×0 = 0. So it is divisible by 3.

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

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

• ( n + 1 )³ + 2( n + 1 ) = ( n³ + 3n² + 3n + 1 ) + ( 2n + 2 ) Just some simplifying
• = ( n³ + 2n ) + ( 3n² + 3n + 3 ) simplifying and regrouping
• = ( n³ + 2n ) + 3( n² + n + 1 ) factored out the 3

which is divisible by 3, because ( n³ + 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³ + 2n ) + 3( n² + n + 1 ) is divisible by 3.

Answer 1

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.

Answer 2

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

Answer 3

Why don't you just test the validity of this using modular arithmetic? I.e. take n congruent to 1 mod 3 and we easily get 3=0. If you try n congruent to 2 mod 3, you get 8+4 =12 =0, so you're done. No ugly inductions (although this particular case is not so dirty).

A useful idea when thinking of induction is to think of dominos. If you know something is true for one fixed tile and if you know that it being true for one tile means that it's true for the neighbour on the right, then it's like knocking one over knocks them all over.

Answer 4

Alternatively, $f:{\mathbb N} \rightarrow {\mathbb Z}/3{\mathbb Z} \;$ is constant since $f(n+1) = f(n)$, so $f(n) = f(0) = 0$. This reduces the induction to a trivial lemma: $f(n)$ is constant if $f(n+1) = f(n)$ for all $n\in \mathbb N$, a trivial telescopy.

Answer 5

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

Answer 6

$$ \begin{align} n^3+2n &= n(n^2+2) \\ &= n(n^2−1+3)\\ &= n((n^2−1^2)+3)\\ &= n((n−1)(n+1)+3)\\ &= n(n−1)(n+1)+3n \end{align} $$

The key is to identify the factor $(n^2-1^2)=(n-1)(n+1)$. Looking at the result you can tell that it must be divisable by 3 because one of $n$, $(n-1)$ or $(n+1)$ is a multiple of 3. Ben Albert gives a similar solution but I believe $3n^2$ should be $3n$ instead.

Answer 7

In a proof by induction, we try to prove that a statement is true for all integers n. To do this, we first check the base case, which is the "Basic Step" above. Then, we have the induction hypothesis, where we assume that the statement is true for an integer k. Using this fact, we prove that the statement is also true for the next integer k+1. This produces a bootstrapping ladder where we use the base case (n=1) to show that the statement is true for n=2 via the inductive hypothesis, and then for n=3, etc, off to infinity; this shows that the statement is true for all integers n.

Here, we claimed that ( n³ + 2n ) + 3( n² + n + 1 ) is divisible by 3 because this was the inductive hypothesis; we were using this to show that ( (n+1)³ + 2(n+1) ) + 3( (n+1)² + (n+1) + 1 ).

Answer 8

Given the $n$th case, you want to consider the $(n+1)$th case, which involves the number $(n+1)^3 + 2(n+1)$. If you know that $n^3+2n$ is divisible by $3$, you can prove $(n+1)^3 + 2(n+1)$ is divisible by $3$ if you can show the difference between the two is divisible by $3$. So find the difference, and then simplify it, and then consider how to prove it's divisible by $3$.

Answer 9

The driving force behind induction is that you show that a base case (when $n = 1$, for example). Then you show that the hypothesis being true at some $k$ implies that it holds at $k+1$. Then, since you have verified the hypothesis at $n = 1$, you have it at $n = 2$. Then, since it holds at $n = 2$, it holds at $n = 3$, and so on. Note that the domain over which the hypothesis holds should be defined in the hypothesis itself.

Now, for your specific case, let's see how this works.

First, for the base case ($n = 1$), we see the following:

$$1^3 + 2 \cdot 1 = 3.$$

That is clearly divisible by $3$, so we have our base case.

Now assume that for all $k \geq 1$, $k^3 + 2k$ is divisible by $3$.

Then for $n = k + 1$, we have:

$$(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = k^3 + 3k^2 + 5k + 3$$

The $3k^2 + 3$ portion is clearly divisible by $3$, so we need only show that $k^3 + 5k$ is divisible by $3$. From the assumption above, we know that $k^3 + 2k = 3m$ for some positive integer $m$. Then,

$$k^3 + 5k = k^3 + 2k + 3k = 3m + 3k = 3(m + k),$$

so the hypothesis holds at $n = k+1$.

Thus, we have for all $n \geq 1$, $n^3 + 2n$ is divisible by $3$.

As the others have suggested, there are certainly other ways of showing the $(k+1)$th case, but hopefully this overall form helps you see how mathematical induction works.

Answer 10

Take base cases 1, 2, and 3, and then deduce case $n+3$ from case $n$.

Answer 11

Hint: if $\:f(n+1) = f(n) + 3\: g(n)\:$ for $\:g(n)\in \mathbb Z,\:$ then $\:3$ divides $f(n)\ \Rightarrow\ 3$ divides $f(n+1)$.

See here for how to view this as a special case of the more general method of telescopy.