4
$\begingroup$

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

so now next step i am not able to solve please help.

$\endgroup$
  • 1
    $\begingroup$ $(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. $\endgroup$ – E W H Lee Sep 8 '14 at 14:41
  • 1
    $\begingroup$ Do you know that $(a+b)^3=a^3+3a^2b+3ab^2+b^3$? ${}\qquad{}$ $\endgroup$ – Michael Hardy Sep 8 '14 at 14:42
  • $\begingroup$ Why do you want to prove it by induction? $\endgroup$ – almagest Sep 8 '14 at 14:46
7
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ =$$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 ? $\endgroup$ – Kartik Shah Sep 8 '14 at 15:11
  • $\begingroup$ ...=$3(m+n+n^2+1)$. This number is divisible by 3 (the quotient is $m+n+n^2+1$) $\endgroup$ – Marm Sep 8 '14 at 15:21
  • $\begingroup$ 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 ! $\endgroup$ – Kartik Shah Sep 8 '14 at 15:28
  • $\begingroup$ You defined m, not me. m=n^3+2n, so actually we only have one variable, as you wish... $\endgroup$ – Marm Sep 8 '14 at 15:34
  • $\begingroup$ 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 ? $\endgroup$ – Kartik Shah Sep 8 '14 at 16:01
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 '|' $\endgroup$ – Kartik Shah Sep 8 '14 at 15:00
  • $\begingroup$ Expand the LHS. $a\mid b$ means "a divides b", or "b is a multiple of a". $\endgroup$ – Jack D'Aurizio Sep 8 '14 at 15:01
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1 Much better. Why do people insist on using induction? $\endgroup$ – almagest Sep 8 '14 at 14:47
  • 1
    $\begingroup$ 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. $\endgroup$ – gnasher729 Sep 8 '14 at 15:31
3
$\begingroup$

$\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}$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

$\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}

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.