# Math Help - Prove that the binomial coefficient is always a natural number?

1. ## Prove that the binomial coefficient is always a natural number?

So say we have the binomial coefficient of n (on the top) and k ( on the bottom) and this text book says to prove by induction that the binomial coefficient is always a natural number, but how can I prove something by indunction when there are two variables involved? Do I only need to use induction on one of the variables? And also, how would I go about actually "starting up" my induction argument? Thanks in advance.

2. Originally Posted by mfetch22
So say we have the binomial coefficient of n (on the top) and k ( on the bottom) and this text book says to prove by induction that the binomial coefficient is always a natural number, but how can I prove something by indunction when there are two variables involved? Do I only need to use induction on one of the variables? And also, how would I go about actually "starting up" my induction argument? Thanks in advance.
Combinatorial proof:

It is the number of combination of k elements from group of n (natural number) = n choose k.

3. A.S.Z's combinatorial proof is correct, but it sounds like you are supposed to provide an inductive proof.

Do you know this identity?

$\binom{n}{m} + \binom{n}{m+1} = \binom{n+1}{m+1}$

If so, you might use it as the basis of your proof.