Prove by induction that $n(n+1)(n+5)$ is multiple of $3.$

Question

$n(n+1)(n+5) = 3d$

I cannot figure out how to solve this homework question. A friend gave me a solution I couldn't make sense of, and I hope there's something easier out there. Also, what would be the general approach towards questions of this form?

Answer 1

Since $$\begin{align}(n+1)(n+2)(n+6)-n(n+1)(n+5)&=(n+1)\left\{(n^2+8n+12)-(n^2+5n)\right\}\\&=(n+1)(3n+12)\\&=3(n+1)(n+4)\end{align} $$ we have $$(n+1)(n+2)(n+6)=n(n+1)(n+5)+3(n+1)(n+4).$$

Answer 2

for $n=1$ we get LHS = $n(n+1)(n+5) = 12$ which is divisible by $3$ Now assume that this is true for some $k$

now for $k+1$ case we get LHS =$ (k+1)(k+2)(k+6) =k(k+1)(k+5)+3(k+1)(k+4) $

Now you already know that $k(k+1)(k+5)$ is divisible by $3$ and also $3(k+1)(k+4)$ is divisible by $3$ hence done.

Answer 3

Note that $n(n+1)(n+5) = n(n+1)(n+2+3) = n(n+1)(n+2) + 3n(n+1)$.

Now $n(n+1)(n+2)$ is always a multiple of $3$ and so is $n(n+1)(n+5)$, being a sum of two multiples of $3$.

Answer 4

The general approach to a proof by induction is via a two-steps proof :

(i) Basis : prove that the formula holds for $n=0$ or $n=1$.

In this case we have to start with $n=1$ and we have that : $1(1+1)(1+5)=2 \times 6 = 12 = 3 \times 4$.

Thus, the formula holds with $d=4$.

(ii) Induction step : assume that the formula holds for $n$ and prove it for $n+1$.

In this example, we assume that : $n(n+1)(n+5)=3d_1$ holds, for some $d_1$, and we have to prove that :

$(n+1)[(n+1)+1][(n+1)+5]=3d_2$

holds for some $d_2$.

To do this, we have to "unwind" the LHS in order to rewrite it as : $n(n+1)(n+5) + 3k$ for some suitable $k$.

Applying induction hypotheses, we may conclude that :

$(n+1)[(n+1)+1][(n+1)+5] = n(n+1)(n+5) + 3k = 3d_1 + 3k = 3(d_1+k)$.

This shows that the formula holds for $n+1$ with $d_2= d_1+k$.

Answer 5

The proof can be done without induction, just see that $n$ is of one of the three forms

$n=3k$, $n=3k+1$ or $n=3k+2$. and check each of these cases

Suppose $n=3k$ and $n(n+1)(n+5)=3k(3k+1)(3k+5)=3(k(3k+1)(3k+5))=3d$ where $d=k(3k+1)(3k+5)$,

Next suppose that $n=3k+1$, hence $n(n+1)(n+5)=(3k+1)(3k+2)(3k+6)=3((3k+1)(3k+2)(k+2))=3d$
where $d=(3k+1)(3k+2)(k+2)$,

Finally suppose that $n=3k+2$, hence $n(n+1)(n+5)=(3k+2)(3k+3)(3k+7)=3((3k+2)(k+1)(3k+7))=3d$
where $d=(3k+2)(k+1)(3k+7)$.

Since it works in all three cases it must be true for any $n$

Answer 6

You don't need induction since $n$, $n+1$ and $n+2$ are consecutive, one them is a multiple of $3$. If $n+2$ is a multiple of $3$ then $n+5$ is too and you have your proof. If you really need induction, consider that $$\begin{split}(n+1)(n+1+1)(n+1+5)-n(n+1)(n+5)&=(n+1)\left[(n+2)(n+6)-n(n+5)\right]\\&=(n+1)(n^2+8n+12-n^2-5n)\\&=(n+1)(3n+12)\\&=3(n+1)(n+4)\end{split}$$ and is therefore a multiple of $3$.

Answer 7

For any $n$, either $n$ or $n+1$ or $n+2$ is divisible by $3$ - so the product of these three numbers is divisible by 3. We can offset these three terms by arbitrary multiples of 3 to get a new set like {$n+3p$, $n+1+3q$, $n+2+3r$} and since we just added a multiple of 3, the product of the resulting 3 terms continues to be divisible by 3. In particular (with $p=0,q=0$ and $r=1$), we have product of $n,n+1$ and $n+5$ is divisible by 3.

Answer 8

Suppose for some $n$ that $3|n(n+1)(n+5)$.

Then $3|n(n+1)(n+5)+6(n+1)(n+5) = (n+1)(n+5)(n+6)$.

Furthermore, we must have $3|(n+5)(n+1)(n+6)-3(n+1)(n+6)=(n+1)(n+2)(n+6)$.