2
$\begingroup$

I need to prove that $n(n+1)(n+5)$ is divisible by 6. where $n$ is a natural number. I have used the method of induction. But not successful I got the expression $(k^3+6k^2+5k)+3k^2+15k+12$ when $n=k+1$.

The term inside the bracket is divisible by 6 since we have assumed that the result is true when $n=k$. If we can show that $3k^2+15k+12$ is also divisible by 6, then we are done. But how to proceed?

$\endgroup$
5
  • 3
    $\begingroup$ Given a natural number $n$, note that the factor $n(n+1)$ implies that $n(n+1)(n+5)$ is a multiple of $2$. Also note that between $n$, $n+1$ and $n+5$ at least one of them (and at most too) is a multiple of $3$. Why? How does this help you? $\endgroup$
    – Git Gud
    Mar 6, 2016 at 8:16
  • $\begingroup$ Consider the cases that $k$ is even and $k$ is odd seperately. It is easier, however, to not use induction and instead compute $n (n+1) (n + 5)$ modulo 6. $\endgroup$ Mar 6, 2016 at 8:17
  • 1
    $\begingroup$ For your actual question note that $3k^2+15k+12=3(k^2+5k+4)$ and now I ask you, why is $k^2+5k+4$ even and how does it being even help you? $\endgroup$
    – Git Gud
    Mar 6, 2016 at 8:29
  • $\begingroup$ $3k^{2}+15k+12\equiv 12(k+1)+3k(k+1)$ and $2|k(k+1)$. $\endgroup$ Mar 6, 2016 at 9:29
  • $\begingroup$ $n(n+1)(n+5)\equiv n(n+1)(n-1)\equiv 0\pmod{6}$, because $n(n+1)(n-1)$ is a product of three consecutive integers, so it is divisible by $2$ and $3$. $\endgroup$
    – user236182
    Mar 6, 2016 at 22:13

8 Answers 8

10
$\begingroup$

$$ \begin{align} n(n+1)(n+5) &=n(n+1)(n+2)+3n(n+1)\\[6pt] &=6\binom{n+2}{3}+6\binom{n+1}{2} \end{align} $$


Binomial Coefficient Basics

If, instead of Pascal's Triangle, we define the binomial coefficients as $$ \binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!} $$ Then we have $$ \begin{align} \binom{n-1}{k}+\binom{n-1}{k-1} &=\binom{n-1}{k-1}\frac{n-k}k+\binom{n-1}{k-1}\\ &=\binom{n-1}{k-1}\frac nk\\ &=\binom{n}{k} \end{align} $$ Thus, if $\binom{n-1}{k}\in\mathbb{Z}$ for all $k\in\mathbb{Z}$, then $\binom{n}{k}\in\mathbb{Z}$ for all $k\in\mathbb{Z}$.

$\endgroup$
4
  • $\begingroup$ Induction on $n$ with $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$. I am assuming that the reader knows a bit about binomial coefficients. This could be very difficult if we don't use any previous results. $\endgroup$
    – robjohn
    Mar 6, 2016 at 17:05
  • $\begingroup$ Rob, yes, I suppose that it is a reasonable assumption (i.e., that the reader knows something about the BC's) - especially given the context of the question here. +1 for a very efficient solution. $\endgroup$
    – Mark Viola
    Mar 6, 2016 at 17:15
  • $\begingroup$ @Dr.MV: I have included an addendum regarding the standard recursion from a more applicable point of view. $\endgroup$
    – robjohn
    Mar 6, 2016 at 18:54
  • $\begingroup$ Excellent ... as always! Wish I could give another vote up. ;-)) $\endgroup$
    – Mark Viola
    Mar 6, 2016 at 21:33
2
$\begingroup$

Since we can easily see that $3k^2+15k+12=3(k^2+5k+4)$ is divisible by $3$, it remains to show that it is divisible by $2$.

It suffices to look at $$k^2+k=3k^2+15k+12-2(k^2+7k+6)$$and this is even because $k^2+k=k(k+1)$ is the product of two consecutive natural numbers, and therefore divisible by $2$.

You may also go deeper and prove that $k^2+k$ is even using induction, of course. It will then be induction-within-an-induction.

$\endgroup$
1
$\begingroup$

$$n(n+1)(n+5)=n^3+6n^2+5n\equiv n^3-n\pmod6$$

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

and use The product of n consecutive integers is divisible by n factorial

$\endgroup$
1
$\begingroup$

One number among $n$, $n+1$, $n+2$ is a multiple of 3.

Since $5 \pmod 3 \equiv 2$, among $n$, $n+1$ and $n+5$, one is a multiple of 3.

Either $n$ or $n+1$ must be an even number (since they are consecutive numbers).

Therefore, n(n+1)(n+5) is a multiple of 2.

As $n(n+1)(n+5)$ is a has both 3 and 2 as factors, it is a multiple of 6.

$\endgroup$
2
  • $\begingroup$ As your approach is slightly different from the other answers (and, perhaps, more intuitive), I laud your answer. However, your formatting is a little bizarre (I've tried to clean it up a little---you can roll back the edit if you really don't like it), and your argument is a little unclear (in the fourth line, for example, the pronoun "it" is ambiguous; by "it" do you mean the original polynomial?). I think that it might be a good idea to spend a little bit of editing your answer to add a little bit of exposition and clear up some of the ambiguity. $\endgroup$
    – Xander Henderson
    Sep 11, 2018 at 22:16
  • $\begingroup$ Thanks, @XanderHenderson I have also tried to remove some ambiguity. One major reason why my approach is different from the other approaches is that I do not know/understand how the other approaches work. $\endgroup$ Sep 16, 2018 at 12:58
0
$\begingroup$

Continuing from your start, let $k^3+6k^2+5k=6p$ for some $p\in\mathbb Z$.

Now, $$(k+1)(k+2)(k+6)=(k^3+6k^2+5k)+3k^2+15k+12=6p+3k^2+15k+12=6p+3(k^2+5k+4)=6p+3(k+1)(k+4)$$


Case 1: $k$ is even.

Then, $k+4$ is also even. We can thus write $k+4=2q$ for some $q\in\mathbb Z$.

Hence, $$6p+3(k+1)(k+4)=6p+3(k+1)(2q)=6p+6q(k+1)=6(p+q(k+1))$$ where $(p+q(k+1))\in\mathbb Z$.

Thus, the statement is true when $k$ is even.


Case 2: $k$ is odd.

Then, $k+1$ is even. We can thus write $k+1=2q$ for some $q\in\mathbb Z$.

Hence, $$6p+3(k+1)(k+4)=6p+3(k+4)(2q)=6p+6q(k+4)=6(p+q(k+4))$$ where $(p+q(k+4))\in\mathbb Z$.

Thus, the statement is true when $k$ is odd.

$\endgroup$
0
$\begingroup$

Suppose $n$ is a multiple of 6. Then we are done. Suppose $n$ is neither a multiple of 2 or 3. Then $n+1$ must be even, and if $n+1$ is still not a multiple of 3 then $n+5$ is. Note $n+5\equiv n+2$ (mod 3) and since neither $n$ nor $n+1$ is a multiple of 3, then $n+2$ is. If $n$ is even but not a multiple of 3, we proceed the same way to show either $n+1$ or $n+2$ is. The only case left is when $n$ is an odd multiple of 3 then $n+1$ is even and we are done. In any case, we get a factor of 2 and a factor of 3.

$\endgroup$
0
$\begingroup$

You are almost done! Take $3k^2+15k+12$ modulo $6$ to reduce it to proving that $3k(k+1)$ is divisible by $6$. We already have a factor of $3$, so it suffices to show that $k(k+1)$ must be even. But out of any two consecutive numbers exactly one must be even, so their product must be even too; we are done.

$\endgroup$
-1
$\begingroup$

You just needed one more step. $$\begin{align}n(n+1)(n+5) = & (n+1)(n+2)(n+6) \\ = & n^3+9 n^2+20 n+12 \\ = & (n^3+6n^2+5n)+3n^2+15n+12 \\ = & n(n+1)(n+5)+\underbrace{3n(n+5)}_{\star}+12\end{align}$$

$\bigstar$ If $n$ is even, then $3n$ is divisible by 6, otherwise $n$ is odd and $3(n+5)$ is divisible by 6.


Of course you could have done this immediately.

  • $n(n+1)$ is divisible by $2$.
  • If neither $n$ nor $n+1$ are divisible by $3$, then $n+2$ and $n+5$ will be.
    • exactly one of the three factors, $n$, $n+1$, $n+5$ is divisible by $3$.
  • Therefore $n(n+1)(n+5)$ is divisible by $2$ and $3$, and thus by $6$.
$\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.