# 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}$$ – J. M. isn't a mathematician 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". – Gone 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.

• 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 – Antonio May 1 '18 at 22:52
• Unfortunately this fails for negative integers, if we use the factorial definition of binomial coefficients. – user3932000 Feb 2 at 21:34

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. – darij grinberg Feb 16 '19 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. – darij grinberg Feb 19 '19 at 10:27
• I may be wrong, but shouldn't the sum be over $0\leq r\leq m-1$? – lukeuser Nov 26 '19 at 21:53
• Can you explain Knuth's notation? – James Ensor Mar 11 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. – Gone Nov 27 '10 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. – darij grinberg Feb 16 '19 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$. – darij grinberg Feb 19 '19 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!\$ – Gone Feb 20 '19 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. – darij grinberg Feb 21 '19 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). – Gone Feb 21 '19 at 1:05