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?

  • 1
    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$.2012-10-11

3 Answers 3

6

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.

  • 2
    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.2016-08-01
2

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

  • 0
    @Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test).2015-11-23
1

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