3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 4, 2012 at 3:24
  • $\begingroup$ 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. $\endgroup$ Commented Oct 4, 2012 at 3:28

1 Answer 1

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$ Commented Sep 18, 2015 at 23:07
  • $\begingroup$ @darij: Thanks (and for the other one, too). $\endgroup$ Commented Sep 18, 2015 at 23:15

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.