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$ 15 Answers
$\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 $\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$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$ $\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$ $\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.
