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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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.

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.

Log in to reply

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

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?

Log in to reply

Log in to reply

Log in to reply