# Thread: Bijective Proof Involving Binomial Coefficients

1. ## Bijective Proof Involving Binomial Coefficients

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

$\displaystyle 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 $\displaystyle L(a, b) = \binom{a+b}{b}$, where $\displaystyle L(a, b)$ is the set of lattice paths from (0, 0) to (a, b). Any suggestions?

2. ## 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.

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.