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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 6 down vote accepted

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


share|cite|improve this answer
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 '15 at 23:07
@darij: Thanks (and for the other one, too). – Brian M. Scott Sep 18 '15 at 23:15

Your Answer


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.