Proving combination is a natural number by induction

[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

 

[PeroK]

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

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

 

[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 want to 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.

 

[PeroK]

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 want to 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.

How do you construct Pascal's Triangle?

 

[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?

 

[PeroK]

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?

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

 

[Kariege]

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

 

[PeroK]

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

Can you state your inductive hypothesis?

There is no algebra or any calculations required.

 

[Kariege]

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

 

[PeroK]

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

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.