Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by induction: nCr always an integer

  1. Jan 30, 2005 #1
    Hello all,

    I've been asked for a graduate level course to do a proof using induction that shows that nCr always turns out to be an integer. I thought that I might use Pascal's triangle somehow and the fact that nCr is equal to n! / r!(n-r)! (I saw a brief explanation of this while doing a web search) but am not sure how to lay out the proof. This seems really really complicated... am I wrong? Any help will be much appreciated.

    Best regards,
    SG
     
  2. jcsd
  3. Jan 30, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If you can prove nCr is an element of Pascal's triangle, then the rest of the proof is trivial...
     
  4. Jan 30, 2005 #3
    Re: Proof

    I'm not sure I know how to prove that...
     
  5. Jan 30, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So what definition of nCr are you using?
     
  6. Jan 30, 2005 #5
    Proof: nCr

    I am using the definition that nCr = n! / r! (n-r)!

    Steve

    P.S. Thank you for your help...
     
  7. Jan 30, 2005 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So, you just need to prove that formula satisfies the initial conditions and recurrence relation of Pascal's triangle.
     
  8. Jan 30, 2005 #7
    So, the initial conditions would be n=0, r=0?

    And then what would I take as my induction hypothesis?

    Steve
     
  9. Jan 30, 2005 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Can you write, algebraically, how to compute Pascal's triangle?
     
  10. Jan 30, 2005 #9
    Would I do it as some sort of a matrix?

    Steve
     
  11. Jan 31, 2005 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The binomial coefficients satisfy something called a recurrence relation. Surely you've seen this? How do you find nCr, as en entry in pascal's triangle, from other entries, specifically ones higher up in the triangle, even more specifically the ones immediately above it. (I'm assuming that 1C1 is at the top and the triangle cascades down.)

    If you don't mind me asking, where is this a graduate level question?
     
  12. Jan 31, 2005 #11
    Re: Proof

    No problem. I am in a graduate program for secondary mathematics education in New York City. I'm in a "computers for mathematics teachers" course--we're learning to use Maple--and this is part of the first week's assignment.

    Thanks for your input.

    Steven
     
  13. Jan 31, 2005 #12
    Re: Proof

    P.S. I do know how Pascal's triangle is constructed and how it is used in binomial expansions, but wasn't sure how to write this up in a proof.

    Steven
     
  14. Jan 31, 2005 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Well it would go something like.

    0Cr is an integer, for all r (1 if r=0, and zero otherwise). Suppose that for a given n, all the nCr are integers, then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are integers for all r. Hence, by induction, nCr is an integer for all n and all r.
     
  15. Jan 31, 2005 #14
    sgnagni:I do know how Pascal's triangle is constructed and how it is used in binomial expansions, but wasn't sure how to write this up in a proof.

    Pascal's triange is a construction useful for getting ideas here, and some have used it for computation. But a proof that is algebraic is most likely based on algebraic considerations, as matt grime has shown.
     
  16. Feb 1, 2005 #15
    Thanks

    OK, thanks much to all. I think this gives me enough to proceed.

    All best,
    Steve
     
  17. Feb 1, 2005 #16

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    well there are n! ways toa rrange n thigns in a sequence. but one can accomplish this by first choosing a subset of r thigns from among the n thigns. then oine can arrange those r thigns in any order, followed by the remianing n-r thigns in any order.

    since there are r! ways to order the r thigns and (n-r)! bways to arrangenr the n-r thigns, this gives the equation: number of ways to arrange n things = times number of ways to choose r of those things, times r! times (n-r)!

    i.e. n! = nCr (r!)(N-r)!. that does it.
     
  18. Feb 2, 2005 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    but the OP specifically asked for an inductive proof.
     
  19. Feb 6, 2005 #18
    Thanks again all. I did finish up that proof (even wrote it up in Maple!) and sent it off.

    All best,
    sgnagni
     
  20. Nov 18, 2005 #19
    sgnagni i need to prove exactly the same thing u proved before. is there any way you could tell me how to start.? im a little confuse ..plz help
     
  21. Nov 18, 2005 #20

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Surely this thread has suggested places to start?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by induction: nCr always an integer
  1. A Proof by induction (Replies: 4)

  2. Induction Proof (Replies: 3)

  3. Proof By Induction (Replies: 0)

Loading...