# Proving Binomial Identities Using Bijections To Lattice Paths

Let $n$ be a positive integer. 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

Consider lattice paths from $\langle 0,0\rangle$ to $\langle n-1,n\rangle$ in the planar lattice $\mathbb{Z}^2$ using unit steps to the right (i.e., $\langle i,j\rangle \to \langle i+1,j\rangle$) and unit steps to the top (i.e., $\langle i,j\rangle \to \langle i,j+1\rangle$).

For each path $\pi$ from $\langle 0,0\rangle$ to $\langle n,n-1\rangle$ let $r(\pi)$ be the smallest $j$ such that $\langle n,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$ (since the elements in $\Pi_j$ are in bijection with lattice paths from $\langle 0,0\rangle$ to $\langle n-1,j\rangle$, of which there clearly are $\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,n-1\rangle$.

Let $\Pi_j'$ be the paths from $\langle 0,0\rangle$ to $\langle n-1,n\rangle$ that pass through $\langle j,n\rangle$ but not $\langle j-1,n\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-1,n\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\;.$$

-
I have edited your post to correct it (as I think). When you count paths from $\langle 0,0\rangle$ to $\langle n-1,n\rangle$ whose lowest intersection with the line $x=n-1$ is $\langle n-1,j\rangle$ (as you did before my edit), you should get $\dbinom{n-2+j}{j}$, not $\dbinom{n-1+j}{j}$; and then you have to sum from $j=0$ to $n$, not to $n-1$. So I think you solved a different problem there: You proved that $\dbinom{2n}{n} = 2\sum\limits_{j=0}^n \dbinom{n-2+j}{j}$. – darij grinberg Sep 18 at 23:07
@darij: Thanks (and for the other one, too). – Brian M. Scott Sep 18 at 23:15