Waste less time on Facebook — follow Brilliant.
×

Restricted Proof Challenge : Combinatorics

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 :)

Note by Roberto Nicolaides
1 year, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Let'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, 3 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, 3 months ago

Log in to reply

@Michael Mendrin 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. Roberto Nicolaides · 1 year, 3 months ago

Log in to reply

@Roberto Nicolaides The sum of two integers is an integer. The assumption is that for all coefficients for a particular \(n\) are already integers. This then proves that they're all integers for \(n+1\). I can spend more time making this more rigorous, but the essential point is the same. Pascal triangle, remember? If one row is all integers, then so is the next.

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, 3 months ago

Log in to reply

@Michael Mendrin 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? Roberto Nicolaides · 1 year, 3 months ago

Log in to reply

@Roberto Nicolaides 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. Michael Mendrin · 1 year, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...