×

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

Sort by:

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. · 1 year, 7 months ago

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. · 1 year, 7 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. · 1 year, 7 months ago

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? · 1 year, 7 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? · 1 year, 7 months ago