I'm struggling with this problem:
For any natural number $n$, prove that $n^3 + 3n^2 + 2n$ is a multiple of $3$.
That $n^3 + 3n^2 + 2n$ is a multiple of $3$ means that: $n^3 + 3n^2 + 2n = 3 \times k$ where $k \in \mathbb N$ So I tried to find a the number $k$.
The best result I found was: $n^3 + 3n^2 + 2n = n(n+1)(n+2)$ But I'm lagging at the last step, to prove that it is a multiple of $3$.
(However, I got the intuition, If you see the multiples of $3$: $\{0, 3, 6, 9,\dotsc\}$ there is a difference of $3$ between them.
So $n(n+1)(n+2)$ incorporates that difference. This means that if you take a number $n$ then $n$ or $n+1$ or $n+2$ could be a multiple of $3$ and so their multiplication is a multiple of $3$) But I couldn't extend that idea into a consistent mathematical proof.
Also this problem doesn't help either:Proof that $n^3+2n$ is divisible by $3$
$\endgroup$ 24 Answers
$\begingroup$Among three consecutive integers, one must be a multiple of three. Reason: if $n=3k$, we're done. If $n=3k+1$ then $n+2=3j$ is a multiple of three. If $n=3k+2$, then $n+1=3m$ is a multiple of three. In any case, $3\mid n(n+1)(n+2)$.
$\endgroup$ 9 $\begingroup$HINT: $$n^3+3n^2+2n=n^3-n+3n^3+3n\equiv \underbrace{(n-1)n(n+1)}_{\text{ product of three consecutive integers}}\pmod3$$
Among three consecutive integers, on must be divisible by $3$
$\endgroup$ 2 $\begingroup$Yes, you're on the right track and have realized the important points. Now consider using the pigeonhole principle: It's clear that none of the numbers $n$, $n + 1$, $n + 2$ leave the same remainder when divided by $3$, and the remainders lie in $\{0, 1, 2\}$. Three remainders, three distinct numbers: One of them has to be zero.
$\endgroup$ 0 $\begingroup$In response to your inductive proof link to another example, I thought you might find a similar proof useful to prove that $n^3 + 3n^2 + 2n = n(n+1)(n+2)$ is a multiple of $3$ (I will say divisible by 3, you can modify it yourself if you care).
$\textbf{Proof:}$ (by induction on $n$):
For the basis $n=1$, the result is trivial.
Assume the divisibility holds for $n=k$, that is, $$3 \, | \, k(k+1)(k+2).$$
Let $n=k+1$. Then
$$(k+1)(k+2)(k+3)=k(k+1)(k+2) + 3(k+1)(k+2).$$
Now clearly $$3 \, | \, 3(k+1)(k+2),$$ and from our inductive hypothesis, we have that $$3 \, | \, k(k+1)(k+2).$$ Hence $$3 \, | \, (k(k+1)(k+2) + 3(k+1)(k+2)).$$ Therefore $3 \, | \, n(n+1)(n+2)\, \forall \, n \in \mathbb{N}$.
$\endgroup$ 5
