1. ## Mathematical Induction help

Use mathematical induction to prove that 6 divides $\displaystyle n^3-n$, for all natural numbers. (For example, n=0..1..2)

Im confused on how to set this up.

2. Hi

As you've seen, it's easy to check that $\displaystyle 6$ divides $\displaystyle n^3-n$ when $\displaystyle n=0,1\ \text{or}\ 2.$

Now, to prove that for any $\displaystyle k$ in $\displaystyle \mathbb{N},$ we have to assume that for some integer $\displaystyle n\geq 2\ \ 6$ divides $\displaystyle n^3-n,$ and then prove that $\displaystyle 6$ divides $\displaystyle (n+1)^3-(n+1).$

We can write: $\displaystyle n^3-n=n(n^2-1)=n(n+1)(n-1).$

Hence $\displaystyle (n+1)^3-(n+1)=(n+1)(n+2)n$

An integer is divided by $\displaystyle 6$ iff it is divided by $\displaystyle 2$ and $\displaystyle 3,$ and a prime divides a product iff it divides at least a factor.

If $\displaystyle 2$ and $\displaystyle 3$ divide $\displaystyle n$ or $\displaystyle (n+1),$ then they divide $\displaystyle (n+1)^3-(n+1).$
If $\displaystyle 2$ divides $\displaystyle n-1,$ it also divides $\displaystyle n+1$ and then divides $\displaystyle (n+1)^3-(n+1).$
If $\displaystyle 3$ divides $\displaystyle n-1,$ it also divides $\displaystyle n+2$ and then divides $\displaystyle (n+1)^3-(n+1).$

Therefore $\displaystyle 6|(n^3-n)\Rightarrow6|((n+1)^3-(n+1))$

Of course, writing $\displaystyle n^3-n=n(n^2-1)=n(n+1)(n-1)$ gives an immediate but non inductive proof.

Another proof by induction (maybe more comon, try to do it) consists in, when you assume that $\displaystyle 6$ divides $\displaystyle n^3-n,$ develop $\displaystyle (n+1)^3-(n+1)$ and you find something which is a sum of $\displaystyle n^3-n$ and an integer $\displaystyle x.$ If you show that $\displaystyle x$ is divided by $\displaystyle 6,$ then $\displaystyle 6$ divides $\displaystyle n^3-n+x=(n+1)^3-(n+1)$, and you can end your proof.

3. ## Induction

Hello tokio
Originally Posted by tokio
Use mathematical induction to prove that 6 divides $\displaystyle n^3-n$, for all natural numbers. (For example, n=0..1..2)

Im confused on how to set this up.
This is the third (and there's a fourth) induction question you've posted in the last couple of days. We're here to help you learn how to succeed at Mathematics, not to do your homework for you.

I'll start you off:

$\displaystyle P(n)$ is the propositional function: $\displaystyle 6$ divides $\displaystyle n^3 - n$

Now look at the expression $\displaystyle (n+1)^3 - (n+1)$, and, by removing the brackets, simpifying and re-arranging the terms, see if you can prove that $\displaystyle P(n) \Rightarrow P(n+1)$; in other words, that $\displaystyle 6$ divides $\displaystyle (n+1)^3 - (n+1)$.

Show us your working, and, if you can't do it, we'll see about the next stage.

PS I see someone's beaten me to it. But let's see some working next time.

PPS Since you have been given a solution, here's an easier one:

$\displaystyle (n+1)^3 - (n+1) = n^3 +3n^2+3n+1 -n-1$

$\displaystyle = n^3 +3n^2 +2n$

$\displaystyle =(n^3 -n) + 3n^2 +3n$

$\displaystyle =(n^3 -n) +3n(n+1)$

Now one of $\displaystyle n$ and $\displaystyle (n+1)$ is always even. So $\displaystyle 3n(n+1)$ is divisible by $\displaystyle 6$. So $\displaystyle P(n) \Rightarrow (n^3 - n) + 3n(n+1)$ is divisible by $\displaystyle 6 \Rightarrow P(n+1)$.

$\displaystyle P(1)$ is $\displaystyle 1^3 - 1$ is divisible by $\displaystyle 6$, which is true. So $\displaystyle P(n)$ is true $\displaystyle \forall n \in \mathbb{N}$.