Results 1 to 3 of 3

Math Help - Bijective Proof Involving Binomial Coefficients

  1. #1
    Newbie
    Joined
    Jul 2012
    From
    Canada
    Posts
    3

    Bijective Proof Involving Binomial Coefficients

    How can I derive a bijection to show that the following equality holds?

    2\displaystyle\sum\limits_{j=0}^{n-1} \binom{n-1+j}{j} = \binom{2n}{n}

    In class, we've been deriving bijections using lattice paths in-order to order to show that the size of both sets are the same. So for example, in class we've shown that the size of the set  L(a, b) = \binom{a+b}{b} , where  L(a, b) is the set of lattice paths from (0, 0) to (a, b). Any suggestions?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,173
    Thanks
    765

    Re: Bijective Proof Involving Binomial Coefficients

    Hey Nizbel99.

    I don't know about the whole Lattice point thingy, so I can't help you there with regards to that.

    My own conclusion is that the best way to do this is by induction since it's really setup for that kind of thing. Prove the first case then and do the rest of induction.

    The first case is you let n = 1 show its true then show its true for n = k + 1 assuming true for n = k and then if that's done correctly true for all integers n >= 1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2012
    From
    Canada
    Posts
    3

    Re: Bijective Proof Involving Binomial Coefficients

    Sadly, I cannot use any other types of proofs for this question. It must be using bijective correspondances between two sets (which lattice paths work well for). I've managed to prove the other ones on my assignment, but I still have this one to get... Sadly, I haven't made any progress on this since.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Parity proof with binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 24th 2011, 01:57 PM
  2. Proof Involving Binomial Theorem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 27th 2010, 09:33 PM
  3. Proof of a series with binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 25th 2010, 09:08 PM
  4. Sums of Binomial Coefficients - proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 22nd 2010, 08:44 AM
  5. Binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 5th 2008, 12:21 PM

Search Tags


/mathhelpforum @mathhelpforum