Results 1 to 3 of 3

Math Help - [SOLVED] Discrete Math Proof: Combinations

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    2

    [SOLVED] Discrete Math Proof: Combinations

    Hey, first time poster here, this is the proof:
    For positive integers j and k, 1<=j<=k, show that C(k+1,j) = C(k,j) +C(k,j-1)

    I am at the point where I have numerator: [ k!(k-j-1)!(j-1)! + k!j!(k-j)! ]
    over [ j!(j-1)!(k-j-1)!(k-j)! ]

    Which i need to simplify.

    Which is supposed to equal (k+1)! / (j!(k+1-j)!) I believe

    I'm probably making this more confusing than it needs to be.
    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    nCr Formula

    Hello jcbeta730
    Quote Originally Posted by jcbeta730 View Post
    Hey, first time poster here, this is the proof:
    For positive integers j and k, 1<=j<=k, show that C(k+1,j) = C(k,j) +C(k,j-1)

    I am at the point where I have numerator: [ k!(k-j-1)!(j-1)! + k!j!(k-j)! ]
    over [ j!(j-1)!(k-j-1)!(k-j)! ]

    Which i need to simplify.

    Which is supposed to equal (k+1)! / (j!(k+1-j)!) I believe

    I'm probably making this more confusing than it needs to be.
    Thanks in advance.
    Thanks for showing us your working. But you have a sign wrong. You should have

    \binom{k}{j}+\binom{k}{j-1}=\frac{k!}{j!(k-j)!} + \frac{k!}{(j-1)!(k-[j-1])!}

    =\frac{k!}{j!(k-j)!} + \frac{k!}{(j-1)!(k-j\color{red}+\color{black}1)!}

    =\frac{k!(j-1)!(k-j+1)!+k!j!(k-j)!}{j!(k-j)!(j-1)!(k-j+1)!}

    What you need to do now is to factorise the numerator.

    You've obviously got a common factor of k!.

    What is less obvious is that j! and (j-1)! have a common factor of (j-1)!. This is because j! = (j-1)! \times j.

    And, in the same way, (k-j+1)! = (k- j)! \times (k-j+1).

    In all, then, you can take out a common factor k!(j-1)!(k-j)! from the two terms in the numerator to get:

    \frac{k!(j-1)!(k-j+1)!+k!j!(k-j)!}{j!(k-j)!(j-1)!(k-j+1)!}= \frac{ k!(j-1)!(k-j)!([k-j+1] + j)}{ j!(k-j)!(j-1)!(k-j+1)!}

    =\frac{k!(k+1)}{j!(k+1-j)!}

    =\frac{(k+1)!}{j!([k+1]-j)!}

    =\binom{k+1}{j}

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2009
    Posts
    2
    Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] discrete math help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 23rd 2009, 12:30 PM
  2. [SOLVED] discrete math help for B union E
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 6th 2009, 08:30 AM
  3. discrete math proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 5th 2008, 11:56 AM
  4. I need some help with a discrete math proof
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: September 28th 2008, 07:49 AM
  5. Discrete math (proof by contradiction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 26th 2007, 10:47 AM

Search Tags


/mathhelpforum @mathhelpforum