For all integers $n \ge 1$, prove 6 divides $n(n+1)(n+2)$ by PMI.

Question

For all integers $n \ge 1$, prove 6 divides $n(n+1)(n+2)$ by PMI.

I check for my base case, it holds.

Then, my inductive hypothesis that for any arbitrary $n \ge 1$, 6 divides $n(n+1)(n+2)$ so there exists integer $k$ s.t $n(n+1)(n +2) = 6k$. Assume $(n+1)(n+2)= 6k/n$.

Inductive step: $(n+1)(n+1+1)(n+1+2) = (n+1)(n+2)(n+3)=(6k/n)(n+3)= 6k + (18k/n)$.

From here I can simply factor out a $6$ but how do I know that $18k/n$ is an integer?

I also struggle when it comes to the substitution part. When there is one $n$ involve is simple but when I see various $n$'s in my equation I'm unsure about which one I really want substitute for, any pointers?

Lastly, am I allowed to make various substitutions or am I confined to only substitute once? Thank you for your time.

Answer 1

Note: You may prove your result directly by noting that among $n,(n+1)$, and $(n+2)$, one is a multiple of $3$ and at least one is even, yielding a factor of $6$. However, an inductive proof is still quite possible. Just something useful to keep in mind.

For each $n\geq 1$, let $S(n)$ denote the statement $$ S(n) : 6\mid n(n+1)(n+2). $$ Base step: Since $6$ divides $6, S(1)$ holds.

Inductive step: Fix some $k\geq 1$, and suppose that $S(k)$ holds; that is, suppose that $\ell\in\mathbb{Z}$ so that $$ k(k+1)(k+2)=6\ell. $$ Then trying to prove $S(k+1)$, \begin{align} (k+1)(k+2)(k+3) &= k(k+1)(k+2)+3(k+1)(k+2)\\[0.5em] &= 6\ell+3(k+1)(k+2), \end{align} and since one of $k+1$ or $k+2$ is even, $6$ divides $3(k+1)(k+2)$, and so $6$ divides $(k+1)((k+1)+1)((k+1)+2)$, proving that $S(k+1)$, and concluding the inductive step that $S(k)\to S(k+1)$.

By PMI, for every $n\geq 1, S(n)$ holds. $\blacksquare$

Answer 2

Here's an alternative: To prove that $(n+1)(n+2)(n+3)$ is divisible by $6$, you just have to prove that $(n+1)(n+2)(n+3)-n(n+1)(n+2)$ is divisible by $6$. And if we compute that last expression we find it to be equal to $3n^2+9n+6=3(n+1)(n+2)$ which is divisible by $3$ and by $2$ (since it is a product of two consecutive integers), hence it is divisible by $6$, the thing that completes the proof.

You may ask yourself why does this method work? The reason can be demonstrated as follows: If $g(n):=(n+1)(n+2)(n+3)-n(n+1)(n+2)$ is divisible by $6$, then that means that there is some $k$ in $\mathbf N$ such that $g(n)=6k$. Now by the inductive hypothesis we have that $n(n+1)(n+2)$ is divisible by $6$, hence there is some $h$ in $\mathbf N$ such that $n(n+1)(n+2)=6h$. So now we can write the very first equality as :

$$ 6k=(n+1)(n+2)(n+3)-6h\iff(n+1)(n+2)(n+3)=6(h+k). $$

Since $h+k\in\mathbf N$, it follows that $(n+1)(n+2)(n+3)$ is divisible by $6$. $$\tag*{$\small\square$}$$

This technique is very powerful in the sense that it works in most cases: If you have an expression $P(n)$ and you want to show that it is divisible by some number $m$, then it all boils down to showing that the base case holds and that $P(n+1)-P(n)$ is divisible by $m$.

Answer 3

Write $$(n+1)(n+2)(n+3) = n(n+1)(n+2) + 3(n+1)(n+2) = 6k +3(n+1)(n+2)$$ and prove by induction that $(n+1)(n+2)$ is divisible by $2$.