2
$\begingroup$

Possible Duplicate:
Proof that a Combination is an integer

I can't think how to prove that ${n\choose k} \in\mathbb{Z}$.

I've played with it for a while, using the factorial definition for ${n\choose k}$. Must be something to do with factors but I'm struggling to prove.

Thanks.

  • 1
    Perhaps you should have a look here: http://math.stackexchange.com/questions/11601/proof-that-a-combination-is-an-integer2011-09-19

1 Answers 1

3

The easiest way is to use the recurrence identity from Pascal triangle

$ \binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k} $ and notice that $\binom{0}{0} = 1$, $\binom{n}{0} = \binom{n}{n} = 1$ for $n \in \mathbb{N} \cup \{ 0 \}$.