How can we prove, without using the properties of binomial coefficients, the product of n consecutive integers is divisible by n factorial?
The product of n consecutive integers is divisible by n! (without using the properties of binomial coefficients)
-
2You could have just edited your previous question... – 2010-11-27
-
0**NOTE** $\ $ This question is *not* an exact duplicate of any prior question. The question *is* interesting with the added proviso to not employ properties of binomial coef's. Note that this proviso was not part of the prior question. The prior question should be closed as a duplicate, but not this one. – 2010-11-27
-
4@Bill: Old questions being closed as dupes of newer ones does not make any sense. We can easily have this edited into the old. Either this one goes or both stay open. IMO, this is so closely related to the previous one, that we should edit this into the old one and close this one. – 2010-11-27
-
1I don't agree. The prior question already has three answers being given to the question without the proviso, i.e. to the nonintended question. Better to close that one since the questions and the answers are all exact duplicates of a prior question. – 2010-11-27
-
0@Bill: And this one also has been answered by one of those answers. I don't see your point. – 2010-11-27
-
0@Moron: This post has the intended question, and only answers to that question. The prior post has the unintended (duplicate) question and mostly answers to that duplicate question. But you think that the duplicate should remain open? Your logic escapes me. – 2010-11-27
-
0@Bill: What intended question? Both questions are very similar and in fact both have been answered by the answers in the other question, which is in fact a super set of this one. I see no point in keeping this open. Especially, when the other (older) one can be edited easily to make it clear that non binom coeff proofs are also sought. Once a question is written it is not cast in stone. It can always be edited. This conversation is pointless. – 2010-11-27
-
0@Moron: This later question with the poviso is what the OP intended - as he indicated in a comment to the prior question, viz. "I wish to obtain a proof which does not use the properties of binomial coefficients". The problem with editing the prior question to change it to this later question is that it then makes most of the answers to that question no longer applicable to the newly edited question. This later question with the proviso *is* a very different question than the former question without it. I think the best solution is to close the prior as a dup and move one answer there here. – 2010-11-27
-
0@Bill: If it was clear from the comments in the other question, why didn't people edit that question and give suitable answers? Very strange. I don't think we should encourage such behaviour, either for OP to create new questions instead of editing or for people to ignore pertinent comments to the question. Anyway... – 2010-11-27
-
0@Moron: My remarks pertain to how to cleanup the two threads. They say nothing about encouraging "such behavior" - whatever that might mean. As for the first question, the OP's clarifying comment was posted *after* the first answer (and after I started composing my answer). Wasn't that obvious? – 2010-11-27
-
0@Bill: If the cleanup is to close an old question as a dupe of a new one, something is wrong somewhere. In this case, it is OP creating a new question instead of editing, and people ignoring comments before answering. As to your comment about obvious, it is not. There was plenty of time between OP commenting and the other answers appearing. As to the behaviour comment, it had nothing to with what you did. It is about trying to have a high signal to noise ratio on this site. We can't have people creating questions and ignoring them, or people giving answers without reading relevant comments. – 2010-11-27
-
0Another thing is people posting answers to questions which ought to be closed as dupes (which is another case of not reading relevant comments here). – 2010-11-27
-
0@Moron: You can't expect every person answering a question to know it is a dupe. Nor can you expect every person to have read every comment (esp. before they were posted!). In this case the best solution is to close the duplicate original, and merge one answer from there here. Apparently you think that doing so would condone the user's behavior of posting a new question. I don't understand why you think that. In any case this is a job for the mods so we should simply let them do what is required. – 2010-11-27
-
3@Bill: What are you talking about? Paolo was well aware that he had posted the older question and even made a comment in that question saying he didn't want proofs involving binomial coefficients. Instead of editing that question, he just opened a new one. That is the behaviour I think should be discouraged. Having multiple questions with minor variations, when one question will do is just increasing the noise in the site. – 2010-11-27
-
0@Moron: Where did you get the strange idea that I endorse posting multiple questions with minor variations? – 2010-11-27
-
0@Bill: Well, then don't answer them! Anyway, I am wasting my time on this minor issue. Please don't expect any more responses from me on this. – 2010-11-27
-
0@Moron: If you choose to "penalize" someone who made an honest mistake by refusing to answer their question then that is certainly your prerogative. But I am here first and foremost to share my knowledge of mathematics by answering questions. So please do refrain from telling me what to do in that regard. – 2010-11-27
4 Answers
You could argue by induction on $n$. The result is obvious if $n=1$.
For the inductive step, assume that $(n-1)!$ divides any product of $n-1$ consecutive integers. Now consider products of $n$ consecutive integers.
Say your product is $P(k)=(k+1)(k+2)\dots(k+n)$. First, you may assume $k\ge0$: If one of the factors $k+j$ is 0, then $P(k)=0$ and obviously $n!$ divides it. If $k+n=-t-1<0$, this is the same as $$(-1)^n(t+1)(t+2)\dots(t+n)=(-1)^nP(t),$$ and $t\ge0$.
Now argue by induction on $k$. The result clearly holds if $k=0$, since $P(0)=n!$.
Suppose $n!|P(k)$. Then $P(k+1)=(k+2)(k+3)\dots(k+n+1)$. Split the last factor as $(k+1)+n$. We have $$P(k+1)=[(k+2)\dots(k+n)](k+1)+[(k+2)\dots(k+n)]n.$$ The first summand is $P(k)$, which is divisible by $n!$ by the inductive assumption on $k$. The second summand is $n$ times a product of $n-1$ consecutive integers, thus $n$ times a multiple of $(n-1)!$, by the inductive assumption on $n$. Clearly, $n$ times a multiple of $(n-1)!$ is a multiple of $n!$, and the sum of two multiples of $n!$ is a multiple of $n!$, so $n!|P(k+1)$.
We are done by induction.
-
0To my understanding, you assume that for some k ≥ 1, for any n ≥ 0, n! divides k(k+1)...(k+n). However, you then claim that (k+1)...(k+n-1) is divisible by (n-1)! which the assumption for k does not imply. May you clarify this? – 2017-08-09
-
0The argument is an induction on $n $. The proof states this explicitly. – 2017-08-09
There is an alternate proof at the following link which uses the result about the highest power of a prime dividing a factorial (scroll down for the proof)
http://2000clicks.com/MathHelp/BasicFactorialConsecutiveIntegerProducts.aspx
-
0At the core, that's the same proof I give in my link, but it lacks the illuminating way of viewing it as a simple rearrangement of fractions. I devised that presentation to make the proof so simple that it can be understood by elementary school students. – 2010-11-27
Since this statement is equivalent to the fact that binomial coefficients are integral it is a bit tricky to make precise the notion of a proof that does not "use properties of binomial coefficients". I will interpret this proviso to mean that the proof is not essentially combinatorial, i.e. it does not employ properties that are immediate from the combinatorial interpretation of binomial coefficients.
In my post here you'll find a purely arithmetical proof that $\rm\: n!\: $ divides the product of $\rm\:n\:$ consecutive integers. The proof shows how to rewrite the associated fraction as a product of fractions whose denominators are all coprime to any given prime $\rm\:p\:$. This implies that no primes divide the denominator (when written in lowest terms), hence the fraction is an integer.
The key property that lies at the heart of this proof is that, among all products of $\rm\: n\:$ consecutive integers, $\rm\ n!\ $ has the least possible power of $\rm\:p\:$ dividing it - for all primes $\rm\:p\:$. Thus $\rm\ n!\ $ divides every product of $\rm\:n\:$ consecutive integers, since it has a smaller power of every prime divisor.
-
0Thank you for the attention you gave to the questions I proposed. I agree with everything you said. I also thank the other participants. Thank you! – 2010-11-27
Let's define $$P(n,k) = \frac{\prod\limits_{i=1}^{n}(k+i)}{n!}$$
If one of the numbers is zero, the product is zero which is divisable by $n!$
If $k < -n < 0$ then, $$P(n,k) = (-1)^nP(n,-k-n)$$
As such it suffices to prove this for non-negative $k$.
Induction:
Base case:
If $n+k = 1$ then $P(n,k) = 0 \in \mathbb{N}$
Inductive step:
Suppose that $P(n,k) \in \mathbb{N}$ for all $n+k = z$
Then for any $P(n,k)$ with $n+k = z+1$, $$\begin{gather} P(n,k) = \frac{\prod\limits_{i=1}^{n-1}(k+i)}{n!}\\ =(k+n)\frac{\prod\limits_{i=1}^{n-1}(k+i)}{n!} \\ =k\frac{\prod\limits_{i=1}^{n-1}(k+i)}{n!} + n\frac{\prod\limits_{i=1}^{n-1}(k+i)}{n!}\\ =\frac{\prod\limits_{i=1}^{n}((k-1)+i)}{n!} + \frac{\prod\limits_{i=1}^{n-1}(k+i)}{(n-1)!}\\ =P(n,k-1) + P(n-1,k) \end{gather} $$
Both terms are natural numbers and hence $P(n,k) \in \mathbb{N}$. This completes the induction and the proof.