6
$\begingroup$

As homework, I have to prove that

$\forall n \in \mathbb{N}: n^3-n$ is divisible by 6

I used induction

1) basis: $A(0): 0^3-0 = 6x$ , $x \in \mathbb{N}_0$ // the 6x states that the result is a multiple of 6, right?

2) requirement: $A(n):n^3-n=6x$

3) statement: $A(n+1): (n+1)^3-(n+1)=6x$

4) step: $n^3-n+(n+1)^3-n=6x+(n+1)^3-n$

So when I resolve that I do get the equation: $n^3-n=6x$ so the statement is true for $\forall n \in \mathbb{N}$

Did I do something wrong or is it that simple?

$\endgroup$
1
  • 1
    $\begingroup$ I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$. $\endgroup$ – Rick Decker Oct 11 '12 at 15:40
7
$\begingroup$

No, your argument is not quite right (or at least not clear to me). You must show that if $A(n)$ is true, then $A(n+1)$ follows. $A(n)$ here is the statement "$n^3-n$ is divisible by $6$". Assuming $A(n)$ is true, then $$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n(n+1)$$ is divisible by $6$ because (1) $n^3-n$ is a multiple of $6$ by assumption, and (2) $3n(n+1)$ is divisible by $6$ because one of $n$ or $n+1$ must be even (this is related to what Alex was pointing out). Therefore $A(n)$ implies $A(n+1)$ and, if $A(n)$ is true for some value of $n$, then all higher integer values of $n$ follow. You correctly showed that $A(0)$ is true.

$\endgroup$
1
  • 2
    $\begingroup$ Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction. $\endgroup$ – mathguy Aug 1 '16 at 13:33
2
$\begingroup$

No need for induction. $$n^3-n=n(n^2-1)=n(n-1)(n+1)$$ which are three consecutive integers. So one must be divisible by 3.


Check for $n=1$: $1^3-1=0=3\cdot 0$

Assume it's true for $n=k$. If you let $n=k+1$ you get $$\begin{align*} (k+1)^3-(k+1)&=k^3+3k^2+2 \\ &=k^3+3k^2+2k\\ &=3\cdot (k^2+k)+(k^3-k)\end{align*}$$ which is divisible by 3

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way. $\endgroup$ – Marco Rauscher Oct 11 '12 at 14:54
  • $\begingroup$ @Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test). $\endgroup$ – yroc Nov 23 '15 at 19:59
1
$\begingroup$

If $n^3-n=6m$,

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

Then, by an auxiliary induction $n^2+n$ is even.

Indeed, $0^2+0$ is even and if $n^2+n=2k$,

$$(n+1)^2+(n+1)=n^2+3n+2=2k+2(n+1)$$ which is even.

Finally, $3$ times an even number is a multiple of $6$.

$\endgroup$
0
$\begingroup$

Proof,

$$6 | (n³ - n) , n ≥ 2$$

Base Case:
If, $$ n = 2 $$ Then $$n³- n = 2³ -2 = 8 - 2 = 6 $$ And 6 | 6, because 6 (1) = 6

Inductive Hypothesis:
Suppose: $$6 | k³ - k $$
Therefore, $$6 | (k+1)³ - (k+1)$$
$$(k + 1)³ - (k + 1) = k³ + 3k² + 3k + 1 - k -1$$ $$= (k³ - k) + (3k² + 3k) = (k³- k) + 3k(k + 1)$$
So we know that 6 | k³- k, because that's what we supposed in the IH.
However, 3k(k+1) must have its own proof.

So,

$$6 | 3n (n + 1)$$

Base Case:
If $$n = 2$$ Then $$3n (n + 1) = 3(2) (2 + 1) = 6 (3) = 18$$

And 6 | 18, because 6 (3) = 18

Inductive Hypothesis:
Suppose: $$6 | 3k (k + 1) $$
Therefore, $$6 | 3 (k + 1) (k + 2)$$

$$3 (k + 1) (k + 2) = 3k² + 9k + 6 = 3k² + 6k + 3k + 6$$ $$= (3k² + 3k) + (6k + 6) = 3k (k + 1) + 6 (k + 1)$$
So we know that 6 | 3k (k + 1), because that's what we supposed in the IH.
And we know that 6 | 6 (k + 1) by definition.

That means that $$6 | 3k(k+1)$$.

Therefore, we can say that $$6 | (k + 1)³ - (k + 1)$$

$\endgroup$
0
$\begingroup$

This answer is with basic induction method...

when n=1, $\ 1^3-1 = 0 = 6.0$

is divided by 6. so when n=1,the answer is correct.

we assume that when n=p , the answer is correct

so we take, $\ p^3-p $ is divided by 6.

then, when n= (p+1),

$$\ (p+1)^3-(p+1) = (P^3+3p^2+3p+1)-(p+1)$$ $$\ =p^3-p+3p^2+3p+1-1 $$ $$\ =(p^3-p)+3p^2+3p $$ $$\ =(p^3-p)+3p(p+1) $$

as we assumed $\ (p^3-p) $ is divided by 6.

$\ 3p(p+1) $ is divided by 3 and as P is a positive integer, P(p+1) is divided by 2, [as n(n+1) is the formula of even numbers].

so 3p(p+1) is divided by 6 too.

so that $\ =(p^3-p)+3p(p+1) $ is divided by 6.

hence, the answer is correct when n=p+1. When n=p the answer is correct too. We proved that the answer is correct when n=1. so as the mathematical induction,
$\ n^3-n $ is divided by 6 for the all positive integers.

$\endgroup$

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.