Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
$$\frac1{n!}\prod_{k=0}^{n-1}(j+k)=\binom{n+j-1}{n}$$ – J. M. 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.

share|cite|improve this 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)}=$



    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.

share|cite|improve this answer

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)!$.

share|cite|improve this answer

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

share|cite|improve this answer
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

The identity below shows that the problem is equivalent to the fact that binomial coefficients are 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

$$\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}$$

share|cite|improve this answer

This answer completely formalizes the argument of Nurdin Takenov in a manner sufficient to easily be expressed in an automated theorem prover such as PVS. Note that this proof uses strong induction on the sum m+k to avoid any nasty double inductions, and is explicit about all assumptions on the arguments:

DEFINITION: *P*roduct of k consecutive posints starting at m (m>=1, k>=1)

i.e. P(m,k) ==def== m...(m+k-1)

LEMMA: P(m,k) = k*P(m,k-1) + P(m-1,k) if m>=2 and k>=2

PROOF: P(m,k) = m...(m+k-1)

    =  m...(m+k-2)[ k + (m-1) ]

    =  k*(m)...(m+k-2)  + (m-1)...(m+k-2)

    =  k*P(m,k-1)      +  P(m-1,k)  QED

THEOREM: Product of k consecutive posints starting with m is divisible by k factorial

i.e. k! | P(m,k)

PROOF (by strong induction on all sums m+k <= n):

(i) BASIS: If n = 2 then clearly m=k=1 and we have k! = 1! clearly divides P(m,k) = 1

(ii) INDUCTION STEP: Assume k! | P(m,k) for all m+k<=n. Now to show that k! | P(m,k) for all m+k <= n+1

If m=1 we are done since P(1,k) = 1...k = k! and if k=1 then k! = 1! clearly divides P(m,k). So in the remainder

we may assume that m >= 2 and k >= 2. Also if m+k<=n we are done vacuously, so consider only that m+k = n+1.

By the lemma we have P(m,k) = k*P(m,k-1) + P(m-1,k) so by the Induction hypothesis we have (k-1)! | P(m,k-1)

and thus also k! | k*P(m,k-1) and also by the Induction hypothesis k! | P(m-1,k) and finally k! | P(m,k) QED

share|cite|improve this answer

For a given prime $p$, the maximum number of times which $p$ can divide $n!$ is $$\sum_{k=1}^\infty \left[{n\over p^k}\right]$$, where $[x]$ is the floor function (to get this result, think about the number of multiples of $p^k$ which do not exceed $n$, and the fact that $p^k$ is a multiple of $p^i$ for each $i\le k$).

(Note that the summation above is actually finite.)

Then, the maximum number of times which $p$ can divide $(m+1)\cdots(m+n)=(m+n)!/m!$ is $$\sum_{k=1}^\infty \left[{m+n\over p^k}\right]-\left[{m\over p^k}\right].$$

Since $[a]+[b]\le[a+b]$, $[(m+n)/p^k]-[m/p^k]\ge[n/p^k]$, so the above is $$\ge\sum_{k=1}^\infty \left[{n\over p^k}\right],$$

which is actually the maximum number of times which $p$ can divide $n!$.

This is true for all prime $p$, so we get $$n!\mid(m+1)\cdots(m+n).$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.