# The product of $n$ consecutive integers is divisible by $n!$ (without using the properties of binomial coefficients)

How can we prove, without using the properties of binomial coefficients, the product of $$n$$ consecutive integers is divisible by $$n$$ factorial?

• You could have just edited your previous question... – J. M. isn't a mathematician Nov 27 '10 at 14:35
• 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. – Bill Dubuque Nov 27 '10 at 15:42
• @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. – Aryabhata Nov 27 '10 at 15:57
• I 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. – Bill Dubuque Nov 27 '10 at 16:04
• @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. – Aryabhata Nov 27 '10 at 23:01

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.

• To 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? – rr01 Aug 9 '17 at 9:18
• The argument is an induction on $n$. The proof states this explicitly. – Andrés E. Caicedo Aug 9 '17 at 11:27
• Apologies if this was evident to everyone but me, but it took a few minutes for me to realise that this was essentially a nice proof of $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ – Alexander51413 Dec 30 '20 at 19:52

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

• At 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. – Bill Dubuque Nov 27 '10 at 16:32

Let's define $$P(n,k) = \frac{\prod\limits_{i=1}^{n}(k+i)}{n!}.$$

If $$n$$ is zero, the product is zero. If $$k$$ is zero, the product is $$n!$$. Both are divisible 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(0,1) = 0 \in \mathbb{N}$$ and $$P(1,0) = 1 \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}(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.

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.

My approach would be to show that for any set of $$n$$ consecutive numbers, working $$\pmod n$$, we can see that: $$\forall t\in1,...,n; \exists r\in0,...,n-1:t|an+r$$

In this sense, $$k=an+b$$ for some $$a,b$$, as we offset the $$\pmod n$$.

This is trivially true because one in every $$t$$ consecutive integers is divisible by $$t$$.

So, if we worked with $$n!=1\cdot2\cdot\ldots\cdot n$$ we match with $$\underbrace{(k+1)(k+2)\ldots(k+n)}_{n \text{ consecutive numbers}}$$, and note that for each $$t\leq n$$ there is a multiple of $$t$$ in each subsection of the product of size $$t$$, and thus the same is true across the whole product.

Almost self contained proof without induction. (Let $$p$$ be an arbitrary prime) We will denote by $$\nu_p$$ the $$p$$-adic valuation and let $$s_p\left(\sum_{j=0}^{n}{a_jp^j}\right)=\sum_{j=0}^{n}{a_j}$$ denote the sum of digits in base $$p$$. We claim that $$\nu_p(n!)=\frac{n-s_p(n)}{p-1}$$ This may be directly verified by subsituting $$n=\sum_{j=1}^{k}{a_jp^j}$$ and using Legendre's formula: $$\nu_p(n!)=\sum_{j=1}^{\infty}{\left\lfloor \frac{n}{p^j} \right\rfloor}$$ This inequality can be easily shown: $$s_p(a+b)\leq s_p(a)+s_p(b)$$ Therefore,$$\nu_p\left(\binom{n}{k}\right)=\nu_p\left(\frac{n!}{k!(n-k)!}\right)=\frac{s_p(k)+s_p(n-k)-s_p(n)}{p-1}\geq 0$$ hence we have proved that $$\binom{n}{k}=\frac{n(n-1)\ldots(n-k+1)}{k!}\in \mathbb{Z}$$ [Using :"If $$x\in\mathbb{Q}$$ such that $$\nu_p(x)\geq 0$$ for all primes $$p$$ then $$x\in \mathbb{Z}$$"]