Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 3 down vote accepted

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\;.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.