1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving combination is a natural number by induction

  1. May 17, 2015 #1
    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. jcsd
  3. May 17, 2015 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You could start by thinking about Pascal's triangle. I hope this isn't homework!
     
  4. May 17, 2015 #3
    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.
     
  5. May 17, 2015 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    How do you construct Pascal's Triangle?
     
  6. May 17, 2015 #5
    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?
     
  7. May 17, 2015 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, right on track. You need to think about induction now.
     
  8. May 17, 2015 #7
    I tried manipulating it but then I ended up nowhere. Could you guide me a little bit?
     
  9. May 17, 2015 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Can you state your inductive hypothesis?

    There is no algebra or any calculations required.
     
  10. May 17, 2015 #9
    Is it (n-1)C(k-1) must be a natural number and (n-1)Ck must also be a natural number?
     
  11. May 17, 2015 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving combination is a natural number by induction
  1. Natural Numbers (Replies: 3)

  2. Natural Numbers (Replies: 11)

  3. Combination of Numbers (Replies: 2)

Loading...