2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Macavity Jul 2 '15 at 4:41
  • $\begingroup$ 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). $\endgroup$ – CIJ Jul 2 '15 at 5:03
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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