# Proving combination is a natural number by induction

Tags:
1. May 17, 2015

### Kariege

Hi,
I've seen on on several sites that you can prove that nCr, where r<=n, is a natural number. I'm not sure how to do this by induction.
So I need help on this proof. How do I write this as a mathematical statement at the start of the induction proof?

Thank you

2. May 17, 2015

### PeroK

You could start by thinking about Pascal's triangle. I hope this isn't homework!

3. May 17, 2015

### Kariege

I'm not sure how to link this to Pascal's triangle to help me to prove. But I'm thinking about proving divisibility, like n! is divisible by r!(n-r)!, or r!(n-r)! is a multiple of n!.I've been wondering how to set up the statement mathematically.
This is not homework. I just wanna know how you're supposed to prove this because induction is quite a foreign concept to me and I've only been able to prove some of the easy ones like formula for series.

4. May 17, 2015

### PeroK

How do you construct Pascal's Triangle?

5. May 17, 2015

### Kariege

you add the two numbers above. so it's nCk=(n-1)C(k-1) + (n-1)Ck.
Then it's (n-1)!/[(k-1)!(n-k)!] + (n-1)!/[k!(n-k-1)!] = nCk
Am I on the right track?

6. May 17, 2015

### PeroK

Yes, right on track. You need to think about induction now.

7. May 17, 2015

### Kariege

I tried manipulating it but then I ended up nowhere. Could you guide me a little bit?

8. May 17, 2015

### PeroK

Can you state your inductive hypothesis?

There is no algebra or any calculations required.

9. May 17, 2015

### Kariege

Is it (n-1)C(k-1) must be a natural number and (n-1)Ck must also be a natural number?

10. May 17, 2015

### PeroK

That's not a hypothesis! But, that is the argument. The inductive hypothesis is:

Assume $\binom{n-1}{k}$ is a whole number for some $n$ and every $k$.

And, the inductive step is to show that this implies that:

$\binom{n}{k}$ is a whole number for every $k$.

There is a minor detail to iron out. Can you see what it is?

Also, you would benefit from writing out a full proof by induction using what you have.