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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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.

- 2 years, 9 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.

- 2 years, 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.

- 2 years, 9 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?

- 2 years, 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?

- 2 years, 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.

- 2 years, 9 months ago