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!

Homework Help: NCr by induction help

  1. Nov 22, 2005 #1
    i have this so far..plz tell me if this is right..do u think this prove is correct

    Let P(n) be the statement that for any n in the natural numbers N, nCr is an element of N for every r with 0<= r<= n
    nCr = n!/(r!(n-r)!)
    0Cr = o!/(r!(0-r)!) = 0( here i dont know wat r is..im guessing r has to be 0 because of the 0<= r<= n)

    so P(0)E(belongs) in N (natural numbers)
    Suppose P(n) is a natural number of any N
    then since {n+1}Cr = nCr + nC{r-1} is true ( already proved it algebraically and i will add it to this part) so it follows that the {n+1}Cr are natural numbers for all n. Hence, by inducion, nCr is a natural number for all n and all r.

    can some one review this prove and tell me if its right? thank you so much for ur help
  2. jcsd
  3. Nov 22, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    0C0 is 1, not 0. apart from that your idea is correct, though you also need to note that nC0 and nCn are integers, otherwise the identity you've written down

    (n+1)Cr = nCr +nC(r-1)

    is no help if r=n+1 or 0 then one of the terms on the left is undefined (by you).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook