Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

marked as duplicate by anon, Alex Becker, Rudy the Reindeer, 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.

Well, for one there's the combinatorial interpretation... – anon Mar 29 '12 at 7:47
please search first… – 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
up vote 6 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|cite|improve this answer

Induction Hint:


$$\qquad \binom{a}{a}=1$$

share|cite|improve this answer

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

share|cite|improve this answer

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