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 struggling with this problem of proof by induction:

For any natural number $n$, prove that $n^3-n$ is a multiple of $3$.

I assumed that $k^3-k=3r$

I want to show that $(k+1)^3-(K+1)=3r$

The final statement is $K^3 +3K^2+2K$

Am I missing something ?

share|improve this question

marked as duplicate by Steven Stadnicki, Najib Idrissi, copper.hat, TZakrevskiy, Seirios Dec 5 '13 at 17:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Stick with $k$ or $K$, not both for the same variable. Plus, if you assume $k^3-k=3r$, you don't want to show that $(k+1)^3-(k+1) = 3r$ but that $(k+1)^3-(k+1)= 3s$ with $s$ some natural number (a priori not the same as $r$ at all). –  Pece Dec 5 '13 at 16:34
add comment

6 Answers 6

up vote 3 down vote accepted

If you have $k^3-k$ divisible by 3, then look at $$(k+1)^3-(k+1)=k^3+3k^2+2k = $$ and this is where you need to spot you can use the inductive hypothesis, because you have a $k^3$ there $$=(k^3-k)+3k^2+3k$$ and the term which doesn't have a coefficient $3$ is divisible by $3$ by the hypothesis.

share|improve this answer
add comment

$n^3-n = (n+1)n(n-1).$ The right hand side is a product of three consecutive integers... For a proof by induction, note that $(n+1)^3-(n+1) - n^3 + n = 3n^2 + 3 n,$ which is obviously divisible by $3.$ So, if you prove the statement for $n=0,$ you are good to go.

share|improve this answer
1  
It's a good proof by not a proof by induction I think. –  user37238 Dec 5 '13 at 16:25
    
Is it considered a proof by induction? –  user113670 Dec 5 '13 at 16:26
    
@user113670 No, it is not a proof by induction. –  Igor Rivin Dec 5 '13 at 16:28
    
but one is added. –  Igor Rivin Dec 5 '13 at 16:30
add comment

Use Fermat's little theorem.

Case1: if n is a multiple of 3 then trivially $n^3 -n$ is a multiple of $3$.

Case 2: If $n$ is not a multiple of $3$ you shall get $n^2 \equiv 1 \pmod 3$. Multiply $n$ and get $n^3 -n \equiv 0 \pmod 3$.

Now get your result.

share|improve this answer
    
@Pratyush Thank you for editing, –  Dutta Dec 5 '13 at 17:08
    
Can you go to chat. I made a room for us. –  Pratyush Sarkar Dec 5 '13 at 17:30
add comment

If you want induction, here you go :

$k^3-k=3m$

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

This should help you i guess..

share|improve this answer
add comment

If $n=0 \mod 3$ then is nothing to prove. Suppose that $(n,3)=1.$ Now it follows from the Ferma litle theorem. We have that $n^3=n \mod 3$ or, in other words, $n^3-n$ is multiple of 3.

share|improve this answer
add comment

using congruence theory we can make easier our steps. Note that if we show $n^3\equiv n [3]$ then we are done. Cause in that case, we shall have $3|n^3-n$ which was asked to prove.

Now any positive integer $n$ gives 0, 1, 2 as remainder when divided by 3. In other words, $n\equiv 0, 1, 2[3]$.

When $n\equiv 0[3]$ then evidently $n^3\equiv 0\equiv n[3]$ so that $n^3\equiv n[3]$ is done.

When $n\equiv 1[3]$ then $n^3\equiv 1[3]$ and hence $n^3-n\equiv 1-1\equiv 0[3]$ so that $n^3\equiv n[3]$ again holds. Finally when $n\equiv 2\equiv -1[3]$ then $n^3\equiv -1[3]$ and then $n^3-n\equiv (-1)-(-1)\equiv 0[3]$ so that $n^3\equiv n[3]$ holds.

Thus we can see that no matter whatever $n\in\mathbb{N}$ we choose we shall always have $n^3\equiv n[3]$ in otherwords $3|n^3-n$.

Done

share|improve this answer
add comment

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