4
$\begingroup$

I'm trying to prove that $6 \mid (n^3 - n)$ where $n$ is a nonnegative integer. I started off by proving the basic step with $P(6)=4$. The next step would be the induction. However I'm having a bit f trouble understanding and using the method. Could someone show me how I would prove the statement and explain to me how I would get the answer. Thanks in advance.

$\endgroup$
6
  • 2
    $\begingroup$ What do you mean the basic step $P(6)=4$? The statement you are trying to prove is that $6\mid n^3-n$, where $n\geq 0$. Thus, your base or "basic" step would be to show that $P(0)$ holds. $\endgroup$ Jan 30, 2015 at 16:31
  • $\begingroup$ oh, i figured i could choose any value for n as long as n > 0 $\endgroup$
    – a22asin
    Jan 30, 2015 at 16:34
  • $\begingroup$ A good metaphor to think about is a big line of dominos standing tall. Your base step would be the first domino, and you knock it over, causing the domino after it to fall over, causing the one after that to fall, causing the one after that to fall, etc... The base case refers to the domino you push, and the induction step is what causes the next one to fall. You prove that if it is true for any arbitrary $n$ that it must be true also for $n+1$. If your base case was not as low as it could be, you would still have some dominoes at the front still standing. $\endgroup$
    – JMoravitz
    Jan 30, 2015 at 16:37
  • 1
    $\begingroup$ Write it like this $n^3-n=n(n+1)(n-1)$. Clearly, for all integers there will be atleast a number divisble by $3$ and a number divisible by $2$. This implies that $6|n^3-n$. $\endgroup$
    – AvZ
    Jan 30, 2015 at 16:38
  • 2
    $\begingroup$ @AvZ That is indeed more elegant. But it is not unthinkable that the OP is restricted to using induction. $\endgroup$
    – drhab
    Jan 30, 2015 at 16:41

4 Answers 4

6
$\begingroup$

Hint $\ $ Let $\,f(n) = n^3-n\,$ The base case is clear $\,6\mid f(0) = 0.\ $ For the inductive step we need to prove that $\,6\mid f(n)\,\Rightarrow\, 6\mid f(n\!+\!1).\,$ For this it suffices to prove that $\,6\,\mid f(n\!+\!1)-f(n)=: g(n)\,$ since then $\,6\mid g(n),f(n)\,\Rightarrow\,6\mid g(n)+f(n) = f(n\!+\!1).\ $ But this is easy

$$ f(n\!+\!1) - f(n)\, =\, (n\!+\!2)\color{#0a0}{(n\!+\!1)n - (n+1)n}(n-1) \,=\, 3\color{#0a0}{n(n+1)}$$

which is divisible by $6$ since $\,n\,$ or $\,n\!+\!1\,$ is even (or, use the same method recursively: note that for $\,p(n) = n(n\!+\!1)\,$ we have $\,2\mid p(0)\,$ and $\,2\mid p(n\!+\!1)-p(n) = 2(n\!+\!1))\,$

Remark $\ $ This is a special case of a powerful general method known as telescopic induction. You can find many more examples in my posts on telescopy.

$\endgroup$
1
  • $\begingroup$ +1 Nice proof and purely by induction if the invitation "or use.." is accepted. $\endgroup$
    – drhab
    Jan 31, 2015 at 9:01
2
$\begingroup$

The statement $P(n)$ you are trying to prove should be

$6$ divides $n^3-n$

and your base case should be $P(0)$, which is

$6$ divides $0^3-0$.

The induction step will be to prove

If $P(n)$ is true, then $P(n+1)$ is also true

which is

If $6$ divides $n^3-n$, then $6$ divides $(n+1)^3-(n+1)$

$\endgroup$
4
  • $\begingroup$ ok, so would i try to simplify 6 divides (n+1)^3-(n+1) so that it equals 6 divides n^3−n? is that how you would prove the case? $\endgroup$
    – a22asin
    Jan 30, 2015 at 16:41
  • $\begingroup$ I think you have the right idea, but I don't know what you mean by 'equals' here. “6 divides $(n+1)^3-(n+1)$” is not a number, so it can't equals anything. It is a statement about the number $n$, which might or might not be true. As I said, you need to show that if “6 divides $n^3-n$” is true, then “6 divides $(n+1)^3-(n+1)$” is also true. $\endgroup$
    – MJD
    Jan 30, 2015 at 16:44
  • $\begingroup$ equals is the wrong term i agree, equivalent might be better? $\endgroup$
    – a22asin
    Jan 30, 2015 at 16:46
  • $\begingroup$ @a22asin If you are bound to use induction then start by proving (with induction) that the statement: "$2$ divides $n(n+1)$ for each nonnegative $n$". Next note that $(n+1)^3-(n+1)=n^3-n+3n(n+1)$ and $6$ divides the terms $n^3-n$ and $3n(n+1)$ $\endgroup$
    – drhab
    Jan 30, 2015 at 16:46
1
$\begingroup$

Special of this answer is that only uses induction. It is not taken for granted that the product of two consecutive numbers is even.

Let $P\left(n\right)$ denote the statement:

$2\mid n\left(n+1\right)$ and $6\mid n^{3}-n$

We will prove by induction that $P(n)$ is true for each nonnegative integer $n$.

It is evident that $P\left(0\right)$ is true: $2\mid0=0\left(0+1\right)$ and $6\mid0=0^{3}-0$.

Assume that $P\left(n\right)$ is true for some nonnegative integer $n$.

To be shown is now that $P\left(n+1\right)$ is true, i.e. that $2\mid\left(n+1\right)\left(n+2\right)$ and $6\mid\left(n+1\right)^{3}-\left(n+1\right)$.

$\left(n+1\right)\left(n+2\right)=n\left(n+1\right)+2\left(n+1\right)$ where $2\mid n\left(n+1\right)$ is true and where of course also $2\mid2\left(n+1\right)$. So we conclude that $2\mid\left(n+1\right)\left(n+2\right)$.

$\left(n+1\right)^{3}-\left(n+1\right)=n^{3}-n+3n\left(n+1\right)$ where $6\mid n^{3}-n$ and also $6\mid3n\left(n+1\right)$ as a direct consequence of $2\mid n\left(n+1\right)$. So we conclude that $6\mid\left(n+1\right)^{3}-\left(n+1\right)$.

Proved is now purely by induction that $P\left(n\right)$ is true for each nonnegative $n$. This implies that $6\mid n^{3}-n$ for each $n$.

$\endgroup$
1
  • $\begingroup$ +1 Note that it is not the only purely inductive proof. Indeed, it is essentially the same same as the (alternative) proof in my answer, see "(or, use...)", except without the telescopy explicitly emphasized $\endgroup$ Jan 31, 2015 at 14:23
0
$\begingroup$

Though this can be proven far more easily without induction, but since you asked for it, here goes...
$$P(1)=1^3-1=0$$
Also,
$6|0$ this implies $P(0)$ is true.
Let $P(n)$ be true for all positive integers.
We now have to prove that $P(n+1)$ is true.
$$P(n+1)=(n+1)^3-(n+1)=n^3+3n^2+2n$$
Furthermore, we can write
$$n(n^2+3n+2)=n(n+1)(n+2)$$
We now essentially have to prove that the product of three consecutive natural numbers is divisible by $6$.
Since $P(n+1)$ just equals the product of three consecutive integers we can see that this will be divisible by $6$ as they can be written as $x(2y)(3z)$ or $x(6y)z$.
This is because there has to be a number divisble by $3$ and another one divisble by $2$ in $3$ consecutive integers. However the same number can be divisible by both. Hence the second case.
Hence proved (by induction).

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