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, 2010 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. Nov 27, 2010 at 14:25
• I wish to obtain a proof which does not use the properties of binomial coefficients. Nov 27, 2010 at 14:25
• @Adrián: It's cool; you elaborated a bit more than I would've, so I've upvoted your answer already. @Paulo: you mean a combinatorial argument or something? Nov 27, 2010 at 14:30
• I have flagged this for mod attention, to merge with the other one. Nov 27, 2010 at 20:50

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.

• It's funny because somebody is using the fact that the product of n consecutive integers is divisible by n to demonstrate that the binomial coefficient is an integer :D math.stackexchange.com/a/11603/393990 May 1, 2018 at 22:52
• Unfortunately this fails for negative integers, if we use the factorial definition of binomial coefficients. Feb 2, 2020 at 21:34
• @user3932000 If all the numbers in the product are negative, then changing all the signs does not affect divisibility. And if the product includes zero the result is trivial. Jun 11, 2022 at 6:50

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.

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

• As stated, this assumes that $m$ is nonnegative. Feb 16, 2019 at 1:56

A clearer version of NurdinTakenov's proof. I prefer Knuth's notation, and falling factorials are nicer to work with:

$$\begin{equation*} m^{\underline{k}} = m (m - 1) \ldots (m - k + 1) \end{equation*}$$

First:

\begin{align*} (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}} \end{align*}

So:

\begin{align*} \sum_{0 \le r \le m - 1} r^{\underline{k}} &= \frac{m^{\underline{k + 1}}}{k + 1} \end{align*}

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:

\begin{align*} m^{\underline{k + 1}} &= (k + 1) \sum_{0 \le r \le m - 1} r^{\underline{k}} \end{align*}

By induction, each term of the sum is divisible by $$k!$$, so the right hand side is divisible by $$(k + 1) k! = (k + 1)!$$.

If $$k > m$$, then one of the factors in $$m^{\underline{k}}$$ is zero, and the result is trivial.

If $$m$$ is negative, it is clear that $$m^{\underline{k}} = (-1)^k \lvert m \rvert^{\underline{k}}$$, extending the above so it covers this case too.

• As it is stated, this proof assumes that $m$ is nonnegative. Feb 19, 2019 at 10:27
• I may be wrong, but shouldn't the sum be over $0\leq r\leq m-1$? Nov 26, 2019 at 21:53
• Can you explain Knuth's notation?
– user295645
Mar 11, 2020 at 11:35

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. Nov 27, 2010 at 15:58

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

• As stated, this argument assumes that we are multiplying posints. Feb 16, 2019 at 1:56

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

• As it is stated, this proof only works for $m\geq n\geq 0$. Feb 19, 2019 at 10:28
• @darij But it's obvious how to reduce to that (or $0$) case, e.g. pull out factors of $-1$ or. alternatively, shift by a sufficiently large multiple of $n!\$ Feb 20, 2019 at 23:18
• I hadn't thought of pulling out $-1$ factors -- good point. Still I'd prefer this mentioned explicitly in the post rather than left to the reader to notice. Feb 21, 2019 at 0:53
• @darij Usually - by design - my hints focus on the essence of the matter and leave trivial matters to the reader. Nowadays I preface them with Hint to make that clear, but I hadn't yet started (consistently) doing that back then (when when the site was only a few months old). Feb 21, 2019 at 1:05