# Proving Binomial Identities Using Bijections To Lattice Paths

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?

I should also mention that this MUST be a bijective proof. I know that I can prove this inductively or algebraically really easily, but this isn't what I need to do.

-
It must be something along the lines of, every path to $(n,n)$ passes through some $(n-1,j)$, but I'm not seeing the details. –  Gerry Myerson Oct 4 '12 at 3:24
I have also noticed that you would be "double counting some paths", which could be why the sum ends at n-1 ... but I am not sure where the factor of 2 comes from either. –  Nizbel99 Oct 4 '12 at 3:28

For each path $\pi$ from $\langle 0,0\rangle$ to $\langle n-1,n\rangle$ let $r(\pi)$ be the smallest $j$ such that $\langle n-1,j\rangle$ is in $\pi$. For $j=0,\dots,n-1$ let $\Pi_j=\{\pi:r(\pi)=j\}$. Then $|\Pi_j|=\binom{n-1+j}j$, so there are
$$\sum_{j=0}^{n-1}|\Pi_j|=\sum_{j=0}^{n-1}\binom{n-1+j}j$$ paths from $\langle 0,0\rangle$ to $\langle n-1,n\rangle$.
Let $\Pi_j'$ be the paths from $\langle 0,0\rangle$ to $\langle n,n-1\rangle$ that pass through $\langle j,n-1\rangle$ but not $\langle j-1,n-1\rangle$; reflection in the diagonal gives a bijection between $\Pi_j'$ and $\Pi_j$, so there are $$\sum_{j=0}^{n-1}|\Pi_j'|=\sum_{j=0}^{n-1}\binom{n-1+j}j$$ paths from $\langle 0,0\rangle$ to $\langle n,n-1\rangle$.
Each path from $\langle 0,0\rangle$ to $\langle n,n\rangle$ passes through exactly one of the points $\langle n,n-1\rangle$ and $\langle n-1,n\rangle$, so
$$\binom{2n}n=2\sum_{j=0}^{n-1}\binom{n-1+j}j\;.$$