Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
$$\frac1{n!}\prod_{k=0}^{n-1}(j+k)=\binom{n+j-1}{n}$$ –  J. M. Nov 27 '10 at 14:15
1  
@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
2  
I wish to obtain a proof which does not use the properties of binomial coefficients. –  Paulo Argolo Nov 27 '10 at 14:25
1  
I have flagged this for mod attention, to merge with the other one. –  Aryabhata Nov 27 '10 at 20:50
1  
@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

6 Answers 6

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

    $=(m+1)(m+2)...(m+k+1)-m(m+1)...(m+k)+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.

share|improve this answer

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

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

share|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

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

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|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].$$ (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)!/n!$ 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|improve this answer

Your Answer

 
discard

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.