# Show that $n^3+2n$ is divisible by 3 for all $n\ge 1$

i want to prove it with mathematical induction :

first i am tried with n=0 then it is divisible by zero then i move to next step change all n with K then i get this product :

$$P(K)=K^3+2K = 3m$$

Note: $3k$ because we multiply any no. with $3$ is divisible by $3$

now , next step i am increase $+1$ in $k$ so i get this step :

$$(K+1)^3 + 2(K+1) = 3m$$

• $(k+1)^3+2(k+1) = k^3+3k^2+3k+1+2k+2 = (k^3+2k)+3(k^2+k+1)$ is divisible by $3$ because $k^3+2k$ is divisible by $3$ by induction hypothesis. – E W H Lee Sep 8 '14 at 14:41
• Do you know that $(a+b)^3=a^3+3a^2b+3ab^2+b^3$? ${}\qquad{}$ – Michael Hardy Sep 8 '14 at 14:42
• Why do you want to prove it by induction? – almagest Sep 8 '14 at 14:46

For the induction step:

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

$n^3+2n$ is divisible by 3 (by assumption) and the last addend is obviusly divisible by 3

Remark: If you want to show a statement for all $n\geq k$ then you prove the statement in the first step for k, not for $0$. (In our case we wont get any problems)

• =$$n^3+2n+3(n+n^2+1)$$ =now i put 3m instead of $$n^3+2n$$ so i get $$3m+3(n+n^2+1)$$ now how to simplify this ? – Kartik Shah Sep 8 '14 at 15:11
• ...=$3(m+n+n^2+1)$. This number is divisible by 3 (the quotient is $m+n+n^2+1$) – Marm Sep 8 '14 at 15:21
• this is not the answer in answer it must be one variable remain in your case m and n two variable remains so it dosen't proved ! – Kartik Shah Sep 8 '14 at 15:28
• You defined m, not me. m=n^3+2n, so actually we only have one variable, as you wish... – Marm Sep 8 '14 at 15:34
• no no you get it wrong yes i define m but then we need to simplify and then remains with one variable 'm' and that's the answer but how that i don't know ? – Kartik Shah Sep 8 '14 at 16:01

$$\left((n+1)^3+2(n+1)\right)-\left(n^3+2n\right) = 3(n^2+n+1)$$ is always a multiple of three, hence if $3\mid (n^3+2n)$, then $3\mid ((n+1)^3+2(n+1)).$

• sorry , but i am not able to understand your answer. how you find 3(n^2+n+1) and what do you mean by this symbol '|' – Kartik Shah Sep 8 '14 at 15:00
• Expand the LHS. $a\mid b$ means "a divides b", or "b is a multiple of a". – Jack D'Aurizio Sep 8 '14 at 15:01

An alternate easier solution: Since $n^3+2n = n(n^2+2) \equiv n(n^2-1) = (n-1)n(n+1) \pmod 3$, for any $n$, either $n$ or $n-1$ or $n+1$ is zero modulo $3$ and so their product is divisible by $3$.

• +1 Much better. Why do people insist on using induction? – almagest Sep 8 '14 at 14:47
• They may do so because there is an integer n and that means induction :-( but in this case the difference between consecutive terms is 3n^2 + 3n + 3 which is obviously divisible by 3 without considering different cases. In the end, you don't know which proof ends up easier until you have done both. – gnasher729 Sep 8 '14 at 15:31

$\begin{eqnarray}{\bf Hint}\ \ \ {\rm mod}\ 3\!:\,\ \color{#0a0}{n^3}\! &\equiv& \color{#c00}n\,\ (\equiv\, -2n) &&{\rm i.e.}\ \ \ P(n)\\ \Rightarrow\ (n\!+\!1)^3\! &=& \color{#0a0}{n^3}\! + \color{lightgrey}{3n^2\!+3n}\!+\!1\\ &\equiv& \color{#c00}n + 1 && {\rm i.e.}\ \ \ P(n\!+\!1)\end{eqnarray}$

Alternatively: $n^3+2n\equiv n^3-n\equiv 0 \pmod 3$, using Fermat's little theorem.

I know you want to prove by induction, but anothter proof would be to observe that every integer is congruent to either 0, 1, or 2 (mod 3). Then we want to see if for every integer n:

$n^3 + 2n \equiv 0\pmod{3}$

Well, take all integers n such that $n \equiv 0\pmod{3}$. Then $n^3 \equiv 0\pmod{3}$ and $2n \equiv 0\pmod{3}$ $\implies n^3 + 2n \equiv 0\pmod{3}$

Take all integers n such that $n \equiv 1\pmod{3}$. Then $n^3 \equiv 1\pmod{3}$ and $2n \equiv 2\pmod{3}$ $\implies n^3 + 2n \equiv 0\pmod{3}$

Take all integers n such that $n \equiv 2\pmod{3}$. Then $n^3 \equiv 2\pmod{3}$ and $2n \equiv 4\equiv1\pmod{3}$ $\implies n^3 + 2n \equiv 0\pmod{3}$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ Lets $\ds{n \equiv 3p + \delta}$ for an integer $\ds{p}$ where $\ds{\delta \in \braces{0,1,2}}$. Then,

\begin{align} n^{3} + 2n& =\pars{27p^{3} + 27p^{2}\delta + 9p\delta^{2} + \delta^{3}} + \pars{6p + 2\delta} \\[3mm]&=\color{#c00000}{\Large 3} \pars{9p^{3} + 9p^{2}\delta + 3p\delta^{2} + 2p} + \underbrace{\pars{\delta^{3} + 2\delta}} _{\ds{\in\ \color{#c00000}{\Large\braces{0,3,12}}}} \end{align}

$$it-is--a-proof-without-induction\\\\M=n^3+2n =\\n^3+2n-3n +(3n)\\=n^-n +(3n) \\=n(n^2-1)=(3n)\\=n(n-1)(n+1) +3n \\=3k +3n\\=3(k+n)=3q$$

• bro, i am doing same like you but at last step it is rule that only one variable remains so what is next step ? – Kartik Shah Sep 8 '14 at 14:59