# Binomial Coefficient Computation by Dividing Consecutive Terms

If I take the binomial coefficient: $$\frac{n!}{k! (n-k)!}$$

and I want to know the result of 10 choose 4 and I proceed to do the computation $$\frac{7*8*9*10}{1*2*3*4}$$ by first dividing and then multiplying(x = 7/1 -> x = (x*8)/2 -> x = (x*9)/3 -> x = (x*10)/4 = 210) how can I prove that 7*8 is divisible by 1*2 and 7*8*9 by 1*2*3, etc...

Why will dividing each consecutive term always result in an integer value?

• A simple proof is that the formula counts the number of ways something can be done, so must evaluate to a natural number. Of course in this case, it may look a bit circular. You could also do induction on $n$ After showing $C(n+1,k)=C(n,k)+C(n,k+1)$. – Macavity Jul 2 '15 at 4:41
• An alternative proof is as follows: first note that the exponent $e_p(n!)$ of a prime $p$ in the prime factorization of $n!$ is equal to $$\sum_{k=1}^{\infty}\left\lfloor{\frac{n}{p^k}}\right\rfloor$$ (it will stop at $k=\left\lfloor{\frac{\log n}{\log p}}\right\rfloor$), where $\lfloor x\rfloor$ denotes the least integer $\leq x.$ Then, it suffices to show that $$\lfloor x+y\rfloor\geq\lfloor x\rfloor+\lfloor y\rfloor,$$ for every $x,y\in\mathbb R$ (this is in fact trivial). – CIJ Jul 2 '15 at 5:03

Are you asking why $i!$ divides $r(r+1)\cdots (r+i-1)$ for all $i$? One way of doing it is to observe that $\frac{r(r+1)\cdots(r+i-1)}{i!}$ is $\binom{r+i-1}{i}$, and the number of ways to choose $i$ objects from $r+i-1$ objects is an integer.

Less attractively, one can prove by a double induction that $i!$ divides $r(r+1)\cdots (r+i-1)$ for all $i$.

You could use prime factorizations. A fraction $\frac{a}{b}$ represents an integer iff $a$ has any prime factor to any power that $b$ has. That measn, if we want to show that it is not an integer, we need to find a prime power factor $p^i$ that goes into $b$ but not into $a$. Below is a "proof" (really more a demonstration) that such a prime factor cannot exist.

Say $p$ is a prime that only appears once in the denominator. That is from the actual factor $p$. That means that the denominator looks something like this: $$1\cdot 2 \cdots (p-1)\cdot p\cdot(p+1)\cdots k$$ but the numerator is also the product of $k \geq p$ consecutive integers, so there must be at least one that contains $p$ as a factor. The same thing goes for any prime that appears both as $p$ and as $2p$ in the denominator: The denominator is a product of $k \geq 2p$ natural numbers, so therefore the numerator is as well, and therefore there are at least two numbers in the numerator that is divisible by $p$.

Even when we get to $p^2$, this works just fine. In this case, the denominator has $p^{p+1}$ as a factor, but not $p^{p+2}$. The numerator is then also a product of $k\geq p^2$, so there are at least $p$ numbers that are divisible by $p$. They are consecutive, so at least one of them has to be divisible by $p^2$ as well. Thus we can count $p^{p+1}$ as a factor of the numerator.

And so on.

Here's an absurdly complicated number theory proof.

There is a theorem that, given prime $p$, the highest power of $p$ which divides $n!$ is equal to:

$$\sum_{i=1}^\infty \left\lfloor\frac n{p^i}\right\rfloor$$

So the fact that the above is true follows by proving for every prime $p$ that:

$$\sum_{i=1}^\infty \left\lfloor\frac n{p^i}\right\rfloor \geq \sum_{i=1}^\infty \left\lfloor\frac k{p^i}\right\rfloor + \sum_{i=1}^\infty \left\lfloor\frac {n-k}{p^i}\right\rfloor$$

Which follows because, in general, for integer $a\geq 1$.

$$\left\lfloor\frac n{a}\right\rfloor\geq \left\lfloor\frac k{a}\right\rfloor + \left\lfloor\frac {n-k}{a}\right\rfloor$$