# The product of n consecutive integers is divisible by n factorial

How can we prove that the product of n consecutive integers is divisible by n factorial?

Note: In this subsequent question and the comments here the OP has clarified that he seeks a proof that "does not use the properties of binomial coefficients". Please post answers in said newer thread so that this incorrectly-posed question may be closed as a duplicate.

-
$$\frac1{n!}\prod_{k=0}^{n-1}(j+k)=\binom{n+j-1}{n}$$ –  Ｊ. Ｍ. Nov 27 '10 at 14:15
@J.M. I didn't realize when I was writing the answer that you put this comment. I guess it would be a nice feature to have the page let you know when a new comment has been added while you're either writing a comment or an answer, just as is done with new answers. –  Adrián Barquero Nov 27 '10 at 14:25
I wish to obtain a proof which does not use the properties of binomial coefficients. –  Paulo Argolo Nov 27 '10 at 14:25
I have flagged this for mod attention, to merge with the other one. –  Aryabhata Nov 27 '10 at 20:50
@Moron: It's a joke. If you're not familiar with US holidays then google "turkey day". –  Bill Dubuque Nov 27 '10 at 23:05

This is almost immediate from the fact that the binomial coefficient $$\binom{k+n}{k}$$ is an integer. Just write the product $(k+1) \cdots (k+n)$ accordingly and you'll have your answer.

-

Let us prove that $m^{(k)}=m(m+1)...(m+k-1)$ is divided by $k!$ for all integer $m$. Induction by $k$.

$k=1$: Every integer $m$ is divided by $1$

$k\to k+1$:

• induction by $m$: $m=0$: $0^{k+1}=0$ is divided by $(k+1)!$

$m\to m+1$: $(m+1)^{(k+1)}=((m+1)^{(k+1)}-m^{(k+1)})+m^{(k+1)}=$

$=(m+1)(m+2)...(m+k+1)-m(m+1)...(m+k)+m^{(k+1)}=$

$(k+1)(m+1)...(m+k)+m^{(k+1)}=(k+1)(m+1)^{(k)}+m^{(k+1)}$

and first term is divided by $(k+1)\cdot k!=(k+1)!$ because of induction by k and the second term is divided by $(k+1)!$ because of induction by $m$

the same works for $m\to m-1$

Update Oops, essentially the same proof found in the thread mentioned in this answer.

-

You might be interested in this blog post of Timothy Gowers:

http://gowers.wordpress.com/2010/09/18/are-these-the-same-proof/

-
Thanks for that link. Note that the other "arithmetical" way of proof referred to by Gowers can be exhibited much more intuitively as a simple rearrangement of a product of fractions - see the linked thread in my answer. This slick proof deserves to be much better known. –  Bill Dubuque Nov 27 '10 at 15:58

A clearer version of NurdinTakenov's proof. I prefer Knuth's notation, and falling factorials are nicer to work with: $$m^{\underline{k}} = m (m - 1) \ldots (m - k + 1)$$

First: $$(m + 1)^{\underline{k}} - m^{\underline{k}} = (m + 1) \cdot m^{\underline{k - 1}} - m^{\underline{k - 1}} \cdot (m - k + 1) \\ = k \cdot m^{\underline{k - 1}}$$ So: $$\sum_{1 \le r \le m} r^{\underline{k}} = \frac{m^{\underline{k + 1}}}{k + 1}$$ Now the proof by induction over $k$ goes through easily:

Base: If $k = 0$, we have that $0! \mid m^{\underline{0}}$, which is just $1 \mid 1$.

Induction: Assume $k! \mid m^{\underline{k}}$ for all $m$. Then: $$m^{\underline{k + 1}} = (k + 1) \sum_{1 \le r \le m} r^{\underline{k}}$$ By induction, each term of the sum is divisible by $k!$, so the right hand side is divisible by $(k + 1) k! = (k + 1)!$.

-
$$\rm\displaystyle\quad\quad {m \choose n}\ =\ \frac{m!/(m-n)!}{n!}\ =\ \frac{m\:(m-1)\:\cdots\:(m-n+1)}{n\:(n-1)\quad\quad\:\cdots\:\quad\quad 1\quad\quad}$$