Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on a task where I'm a bit unsure if the answer I've got is correct.

Here is the task:

Show by induction that the following assertion is true for all natural numbers $n$

$n^3 - n$ is divisible by $3$

Here is my answer:

For $n = 1$,
$n^3 - n = 1 - 1$ which is divisible by $3$

Assume the statement is true for some number $n$, that is, $n^3 - n$ is divisible by $3$. Now,

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

which is $n^3 - n$ plus a multiple of $3$.

Since we assumed that $n^3 - n$ was a multiple of $3$, it follows that $(n + 1)^3 - (n + 1)$ is also a multiple of $3$.

So, since the statement "$n^3 - n$ is divisible by $3$" is true for $n = 1$, and its truth for $n$ implies its truth for $n + 1$, the statement is true for all whole number $n$.

I would appreciate if someone could go through the task and the answer and see if I've done this correctly.

Thanks a lot!

share|improve this question
    
Yes, it's correct –  user2566092 Oct 20 '13 at 16:41
11  
You are right. But one can prove simplier without induction, if you will consider a decomposition $n^3-n=n(n+1)(n-1)$. –  Boris Novikov Oct 20 '13 at 16:43
2  
To add on to Boris' statement: one of $n-1$, $n$ and $n+1$ must be divisible by three since they are three consecutive integers. –  Cameron Williams Oct 20 '13 at 16:44

1 Answer 1

$\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{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$

$$ \pars{n + 1}^{3} - \pars{n + 1} = \pars{n^{3} - n} + 3n\pars{n + 1} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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