30
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ $$\frac1{n!}\prod_{k=0}^{n-1}(j+k)=\binom{n+j-1}{n}$$ $\endgroup$ – J. M. is a poor mathematician Nov 27 '10 at 14:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Adrián Barquero Nov 27 '10 at 14:25
  • 2
    $\begingroup$ I wish to obtain a proof which does not use the properties of binomial coefficients. $\endgroup$ – Paulo Argolo Nov 27 '10 at 14:25
  • 1
    $\begingroup$ I have flagged this for mod attention, to merge with the other one. $\endgroup$ – Aryabhata Nov 27 '10 at 20:50
  • 2
    $\begingroup$ @Moron: It's a joke. If you're not familiar with US holidays then google "turkey day". $\endgroup$ – Bill Dubuque Nov 27 '10 at 23:05
27
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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 $\endgroup$ – Antonio May 1 '18 at 22:52
14
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As stated, this assumes that $m$ is nonnegative. $\endgroup$ – darij grinberg Feb 16 at 1:56
5
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Nov 27 '10 at 15:58
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As it is stated, this proof assumes that $m$ is nonnegative. $\endgroup$ – darij grinberg Feb 19 at 10:27
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As stated, this argument assumes that we are multiplying posints. $\endgroup$ – darij grinberg Feb 16 at 1:56
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As it is stated, this proof only works for $m\geq n\geq 0$. $\endgroup$ – darij grinberg Feb 19 at 10:28
  • $\begingroup$ @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!\ $ $\endgroup$ – Bill Dubuque Feb 20 at 23:18
  • $\begingroup$ 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. $\endgroup$ – darij grinberg Feb 21 at 0:53
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Feb 21 at 1:05

protected by Saad Oct 3 '18 at 11:46

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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