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

Question

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.

Answer 1

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.

Answer 2

The identity below shows that the problem is equivalent to binomial coefficients being integral - for which various proofs are known, e.g. using their recursion, or their well-known combinatorial interpretation, or their minimality in terms of prime divisors - see this prior question

$${m\choose n}\ =\ \frac{m!/(m-n)!}{n!}\ =\ \frac{\overbrace{m\:(m-1)\:\cdots\:(m-n+1)}^{\text{product of $\,n\,$ consecutive integers}}}{n!}\qquad$$

Answer 3

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

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

Answer 4

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)(m+2)...(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.