Here's the challenge.

Prove that \(n\) **choose** k, \[ \binom{n}{k} = \frac{n!}{(n-k)!k!}, \] is always an integer. However, you are **not allowed to use the fact that this is an integer counting function** ie. that this is the way of choosing \(k\) objects from a set of \(n\) objects and therefore an integer.

Leave a proof in the comments :)

## Comments

Sort by:

TopNewestLet's make \(k<= \frac{n}{2}\).

\( \binom{n}{k} = \frac{n!}{(n-k)!k!} = \frac{(n-k+1)(n-k+2)...(n-1)n}{(k)!}\)

We have numbers \((n-k+1) \text{ through } n\) in the numerator and \(1 \text{ through } k\) in the denominator, \(k\) numbers in both cases. Consecutive natural numbers will have its multiples in the range \((n-k+1) \text{ through } n\) which will make it possible for them to simplify. In other words, any set of \(k\) consecutive natural numbers will contain multiples of first \(k\) natural numbers.

It would be intuitive approach to understand why, not exactly the full proof. – Maria Kozlowska · 1 year, 9 months ago

Log in to reply

Let's suppose that all coefficients for a particular \(n\) are integers. Check how this goes

\(\dfrac { n! }{ k!(n-k)! } +\dfrac { n! }{ (k-1)!(n-k+1)! } =\)

\(\dfrac { n! }{ k!(n-k)! } +\dfrac { n!k }{ k!(n-k)!(n-k+1) } =\)

\(\dfrac { n! }{ k!(n-k)! } \left( 1+\dfrac { k }{ n-k+1 } \right) =\)

\(\dfrac { n! }{ k!(n-k)! } \left( \dfrac { n+1 }{ n-k+1 } \right) =\)

\(\dfrac { n! }{ k!(n-k)! } \left( \dfrac { n+1 }{ n+1-k } \right) =\)

\(\dfrac { (n+1)! }{ k!(n+1-k)! } \)

We've proved by induction that the coefficients for \(n+1\) are also all integers. Etc. – Michael Mendrin · 1 year, 9 months ago

Log in to reply

– Roberto Nicolaides · 1 year, 9 months ago

Nice one :) Can you see an intuitive reason why it is an integer (with the restriction still applying) ? I feel like I am missing something obvious.Log in to reply

I suppose you'd like a proof where we can't start with the assumption that any of them are integers? – Michael Mendrin · 1 year, 9 months ago

Log in to reply

– Roberto Nicolaides · 1 year, 9 months ago

The induction argument is great :) But yeah, a proof with out assumption that any of them are integers is what I'm secretly looking for. I'm still always a little surprised that the denominators divide into the numerators every time! This doesn't seem intuitive to me when I just look at the formula. Is this the case for most people?Log in to reply

– Michael Mendrin · 1 year, 9 months ago

I know what you mean. If one isn't familiar with Pascal's triangle, and you're just shown a fraction with factorials in it, how is it that it's an integer every time? Proving it directly takes a bit of effort. It becomes an tedious effort of chasing down the primes, like trying to herd cats.Log in to reply