Prove $\forall n \in \mathbb {N}$, $6\vert (n^3-n)$. (strong induction)

Question

Pretty straight forward idea to be proven here, but trying to grasp the fundamentals of what one would consider "strong induction". Please see my proof below, my questions are: is this a valid proof? Is this stylistically appropriate for a proof via strong induction?

EDIT: Sorry as it was not clear in my original question, but this post was more so to assist in grasping fundamentals of Strong Induction. Although thanks for pointing out the simplistic method of realizing that $(n^3-n)$ is simply the product of three consecutive integers and is thus divisible by a factor of $2$ and $3$.

Q: Prove $\forall n \in \mathbb {N}$, $6\vert (n^3-n)$.

$Proof.$ We will prove this via mathematical induction.

Base Case. Let $n=1$ and observe that $6\vert 0$ is true. Let $n=2$ and observe that $6\vert 6$ is true. Finally, let $n=3$ and observe that $6\vert 24$ is true. Thus for $n\in\mathbb{N}$ where $1\le n \le 3$ our proposition holds.

Inductive Step. Assume our proposition is true for $n=j$ where $1\le j \le k$ and $k \ge 3$. Since $6\vert (k^3-k)$ we know $k^3-k=6l$ for some $l\in\mathbb{Z}$.

Then

$$\begin{align}(k-2)^3-(k-2)&= k^3-6k^2+12k-8-k+2\\ &=(k^3-k)-6k^2+12k-6\\ &=6l-6k^2+12k-6\\ &=6(l-k^2+2k-1). \end{align}$$

Thus $\exists m\in\mathbb{Z},(k-2)^3-(k-2)=6m\Rightarrow 6\vert (k-2)^3-(k-2)$. It follows by mathematical induction that $\forall n \in \mathbb {N}$, $6\vert (n^3-n)$. $\Box$

Answer 1

I'm not sure that I understand your inductive step. You say that for all $j$ such that $1\leq j\leq k, 6|j^3-j$ and $k\geq 3$. Then you should now show that this property holds for $k+1$, that is, $6|(k+1)^3+k+1$. Instead, it looks like you show me that $6|(k-2)^3-(k-2)$.

Instead, consider that $(k+1)^3-(k+1)=k^3+3k^2+2k$ and $(k-1)^3-(k-1)=k^3-3k^2+2k$. Compare the two.

Note that while this isn't the induction you're used to (sometimes called weak induction, or the first principle of induction), this "strong" induction isn't much stronger. The proof only needs the case that $k-1$ has the desired property to show that $k+1$ has the property as well. The idea of strong induction is that you would use the fact that all $j$ from $1$ to $k$ use the desired property.

A good example would be the proof of the fundamental theorem of arithmetic; to show that every number greater than $1$ has a prime factorization, we first say that $2$ is prime (the base case). Now let $k>2$, and say that for all $j$ such that $2\leq j\leq k$, $j$ has a prime factorization. If $k+1$ is prime, it is its own prime factorization. If not, it has a prime factor less than it, say $p$. Then $\frac{k+1}{p}$ has a prime factorization by the strong induction hypothesis, so $k+1$ does as well. Here, the entire assumption for all $j$ is needed, because you don't know exactly what $\frac{k+1}{p}$ is, just that it's less than $k+1$.

Answer 2

Proving by induction.

---

First, show that this is true for $n=1$:

$1^3-1=0$

Second, assume that this is true for $n$:

$n^3-n=6k$

Third, prove that this is true for $n+1$:

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

$n^3+3n^2+2n=$

$n^3+3n^2+3n-n=$

$\color\red{n^3-n}+3n^2+3n=$

$\color\red{6k}+3n^2+3n=$

$3(2k+n^2+n)=$

$3(2k+\color\green{n(n+1)})=$

$3(2k+\color\green{2m})=$

$3(2(k+m))=$

$6(k+m)$

---

Please note that the assumption is used only in the part marked red.

We can replace $n(n+1)$ with $2m$, since either $n$ is even or $n+1$ is even.

Answer 3

One way of casting this as a strong induction proof would be to use the polynomial structure of $n^3-n$ to write the sequence as the solution to a recurrence relation. By giving some thought to delta operators / discrete derivatives (for example, either $\nabla f(n)=f(n)-f(n-1)$ or $\Delta f(n)=f(n+1)-f(n))$ and the fact that they reduce the degree of polynomials by one, we can see that by defining:

$$a_n=n^3-n$$

then with a bit of work, we see that

$$\Delta ^3a_n \equiv 6\implies a_{n+3}-3a_{n+2}+3a_{n+1}-a_{n}=6 \,\forall n$$

So, we can write $n^3-n$ as the unique solution to the recurrence equation:

$$a_{n+3}=3a_{n+2}-3a_{n+1}+a_n+6$$

$$a_0=a_1=0,a_2=6$$

Noting quickly that $a_n$ is a multiple of $6$ for $n=0,1,2$, we assume that this is true for all $n<N$ and seek to prove its truth when $n=N$ (this is the induction).

Now, $a_{N}=3a_{N-1}-3a_{N-2}+a_{N-3}+6$, and since our induction hypothesis says that $a_{N-1},a_{N-2},a_{N-3}$ are all multiples of $6$, it is straightforward to observe that $a_N$ must thus also be a multiple of $6$.

Edit: Actually, one can also go a little further: $\Delta ^4 a_n \equiv 0$, and the first $4$ terms can be checked to be multiples of $6$. The same argument with strong induction shows that all terms will be multiples of $6$. Basically here, we hinge instead upon the recursion $a_{n+4}=4a_{n+3}-6a_{n+2}+4a_{n+1}-a_n$.