# Proof that binomial coefficient is a natural number [duplicate]

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.

-

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

Well, for one there's the combinatorial interpretation... –  anon Mar 29 '12 at 7:47
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

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\;.$$

-

Induction Hint:

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

-

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

-