Proving that an expression divides a number

How do you prove that

$$n(n+1)(n+2)$$

is divisible by 6 by using the method of mathematical induction?

According to my book $$\begin{aligned} (n+1)(n+2)(n+3) &= n(n+1)(n+2)+3(n+1)(n+2)\\ &= 6k + 3*2k'\\ &= 6(k+k')\\ &=6k'' \end{aligned}$$

But I wonder, where does that k come from anyway?

-

3 Answers

The $k$ comes from the induction hypothesis: you are supposed to prove that $(n+1)(n+2)(n+3)$ is divisible by 6 assuming that $n(n+1)(n+2)$ is divisible by 6.

That's from where you get an integer $k$ for which $$n(n+1)(n+2) = 6k.$$

The $k'$ comes from the observation that $(n+1)(n+2)$ is the product of two subsequent numbers. One of which has to be even, so the product is even.

-
Ah, now the k makes sense. The k' still confuses me though. Why to care if a number is even or not? If any number multiplied by 6 instantly becomes divisible by 6 anyway, I think. – Omega Jul 5 '12 at 10:41
The second term in the sum is $3(n+1)(n+2)$. To show that it's divisible by 6 they need to show that $(n+1)(n+2)$ is even and then they substitute $(n+1)(n+2) = 2k'$. – Joni Jul 5 '12 at 10:46
+1 for actually answering the question as asked. Yes, there are easier ways to prove the result without using induction (just observe than one of $n+1$, $n+2$ and $n+3$ must be divisible by 3 and at least one must be even), but that's not what the OP asked about. – Ilmari Karonen Jul 5 '12 at 11:01
It is a bit curious though to use without explanation that $(n+1)(n+2)$ is divisible by $2$ (implicitly checking the possible classes of $n$ modulo $2$), and to not use the very similar argument (checking the possible classes of $n$ modulo $6$) to conclude that $n(n+1)(n+2)$ is divisible by $6$ – Marc van Leeuwen Jul 5 '12 at 11:09

1
@MarcvanLeeuwen: mostly a tribute to how textbooks aren't very good at coming up with good examples of induction, I suspect :) – Ben Millwood Jul 5 '12 at 11:45

Since one number out of every $2$ consecutive integers is divisible by $2$ and one out of every $3$ consecutive integers is divisible by $3$, therefore, in the product of $3$ consecutive integers $n(n+1)(n+2)$, atleast one number is divisible by $2$ and one divisible by $3$ and $\gcd(2,3)=1$ $\implies n(n+1)(n+2)$ is divisible by $2\times3=6$.  You can also do it this way: Since every integer is one of the forms: $6k,6k+1,6k+2,6k+3,6k+4$ or $6k+5$, therefore, possibilities the product of three consecutive numbers is : $$6k(6k+1)(6k+2)=6(k(6k+1)(6k+2))$$ $$(6k+1)(6k+2)(6k+3)=(6k+1)2(3k+1)3(2k+1)=6((6k+1)(3k+1)(2k+1))$$ $$(6k+2)(6k+3)(6k+4)=2(3k+1)3(2k+1)(6k+4)=6((3k+1)(2k+1)(6k+4))$$ $$(6k+3)(6k+4)(6k+5)=3(2k+1)2(3k+2)(6k+5)=6((2k+1)(3k+2)(6k+5)).$$ Thus product of every possible combination of $3$ consecutive integers is coming out to be divisible by $6$.

-

1
I tend to think it unwise to denote multiplication as you did in your first paragraph $2.3=6$. To those of us for whom $.$ is a decimal separator, it looks like a very strange statement indeed... perhaps `\times` is better? – Ben Millwood Jul 5 '12 at 11:47
@Ben Millwood: Thanks for the suggestion. better now?? – Avatar Jul 5 '12 at 11:49
Yep, I'm happy :) – Ben Millwood Jul 5 '12 at 11:49

1
:):):) me too.. – Avatar Jul 5 '12 at 11:50

f(n)=n(n+1)(n+2)

Let f(n) is divisible by 6 be true for n=m.

f(m+1) = (m+1)(m+2)(m+3)=m(m+1)(m+2) + 3(m+1)(m+2) =f(m) + 3(m+1)(m+2). Now, product of two consecutive number is always even. So, the proposition is true for n = m+1 , if it is true for n=m.

By k means there exists an integer k such that n(n+1)(n+2)/6.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 8, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9496472477912903, "perplexity_flag": "head"}