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