8
$\begingroup$

In mathematics one defines:

$\left(\begin{array}{c}n\\k\end{array}\right)=\displaystyle\frac{n!}{k!\cdot (n-k)!}$

This is the number of combinations of $k$ elements from a collection of $n$ elements.

I was wondering if it is possible to prove that the result is an integer in a formal way. It's easy to see that $k!$ in the denominator divides the numerator, but how do you prove that the denominator $k!$ also divides the product of all elements between $n-k+1$ and $n$?

$\endgroup$
12
  • $\begingroup$ Basically what you want to know is why $$ k!\: | \: n(n-1)(n-2)\cdots(n-k+1) $$ right? One approach is looking at prime factors. Show that for any prime, among all $k$ long products of consecutive (natural) numbers, $k!$ is (tied for) the one with least divisibility by $p$. $\endgroup$
    – Arthur
    Oct 7, 2013 at 13:42
  • 5
    $\begingroup$ Hint: Apply complete mathetical induction to prove $${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} $$ $\endgroup$ Oct 7, 2013 at 13:44
  • 1
    $\begingroup$ You say that $\binom{n}{k}$ is the number of combinations of $k$ elements from a collection of $n$ elements [1]. If $x$ is equal to an integer, is it not a proof that $x$ itself is an integer? A formal way to express [1] is Newton's binomial theorem. $\endgroup$
    – Siméon
    Oct 7, 2013 at 13:47
  • $\begingroup$ Excuse my naivety, but for a list of consecutive numbers of length N, won't there alway be a number in the list divisible by each of $1 \dots N$ ? $\endgroup$ Oct 7, 2013 at 13:50
  • 1
    $\begingroup$ @stevemarvell when I stumbled into this problem last year, and searched for a non-combinatorial solution, I eventually used the counting argument for numbers of the form $p^m$ (you need also power of primes: for example for $n=13$ you first show that there is one multiple of 8, then that there are a total of three multiples of 4, and last that there are a total of six multiples of 2) $\endgroup$
    – mau
    Oct 9, 2013 at 7:59

1 Answer 1

7
$\begingroup$

$$ \frac{n!}{k!\cdot (n-k)!} =\frac{n(n-1)\cdots(n-k+1)}{k!} =\frac{(n-k+k)(n-1)\cdots(n-k+1)}{k!}\\ =\frac{(n-1)\cdots(n-k)}{k!}+ \frac{(n-1)\cdots(n-k+1)}{(k-1)!} $$ Now use (double) induction.

This is the relation that defines Pascal's triangle: $${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .