# Bijective Proof Involving Binomial Coefficients

• September 30th 2012, 03:45 PM
Nizbel99
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?
• October 1st 2012, 03:32 AM
chiro
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.
• October 3rd 2012, 07:51 PM
Nizbel99
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.