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$
  • 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$ – Daniel W. Farlow Jan 30 '15 at 16:31
  • $\begingroup$ oh, i figured i could choose any value for n as long as n > 0 $\endgroup$ – a22asin Jan 30 '15 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 '15 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 '15 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 '15 at 16:41
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 Nice proof and purely by induction if the invitation "or use.." is accepted. $\endgroup$ – drhab Jan 31 '15 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)$

| cite | improve this answer | |
$\endgroup$
  • $\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 '15 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 '15 at 16:44
  • $\begingroup$ equals is the wrong term i agree, equivalent might be better? $\endgroup$ – a22asin Jan 30 '15 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 '15 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$.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Bill Dubuque Jan 31 '15 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).

| cite | improve this answer | |
$\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.