Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Proof that a Combination is an integer

What is the proof that the binomial coefficient is a natural number?

$$k\ge0,n\ge k \implies {n \choose k} \in N,$$

I guess it's a pretty simple one, but I just can't find it.

share|improve this question
1  
Well, for one there's the combinatorial interpretation... –  anon Mar 29 '12 at 7:47
2  
please search first math.stackexchange.com/questions/11601/… –  noname1014 Mar 29 '12 at 7:55
    
@Tao, My apologies. I did search first, but I entered "natural number" instead of integer so it didn't show. I didn't search for "integer" because I needed a non-negative integer (natural number). Gonna spend more time searching next time. Thanks, anyway. –  Kornelije Petak Mar 29 '12 at 8:11
add comment

marked as duplicate by anon, Alex Becker, Matt N., Benjamin Lim, Asaf Karagila Mar 29 '12 at 9:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers

up vote 3 down vote accepted

The simplest argument is to show that $\binom{n}k$ is the number of $k$-element subsets of an $n$-element set; since this is obviously a non-negative integer the result is immediate.

To see this, note first that there are clearly $$n(n-1)(n-2)\dots(n-k+1)\tag{1}$$ ways to choose a specific sequence of $k$ distinct elements of an $n$-element set: the first may be any of the $n$ elements, the second may be any of the $n-1$ remaining elements, and so on. It’s convenient to rewrite the expression in $(1)$ as $$\frac{n!}{(n-k)!}\;.\tag{2}$$

Now observe that each $k$-element subset of the original $n$-element set can be arranged in $k!$ different sequences; the argument is exactly the same as the one used to justify $(1)$ above. Thus, expressions $(1)$ and $(2)$ actually count each $k$-element subset $k!$ times, once for each of its permutations. Consequently, the actual number of $k$-element subsets is $$\frac1{k!}\cdot\frac{n!}{(n-k)!}=\frac{n!}{k!(n-k)!}=\binom{n}k\;.$$

share|improve this answer
add comment

Induction Hint:

$$\rm \binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}; \qquad \binom{a}{a}=1 $$

share|improve this answer
add comment

This is obvious from the binomial theorem: $(1+X)^n = \sum_{k=0}^n \binom{n}{k} X^k$.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.