I am tasked to find a combinatorial argument to prove the identity and I'm stumped.


These are the attempts that I've made.

1) Double count the number of non negative integer solutions to

$x_{1}+\cdots +x_{n}=n+1$.

The RHS is trivial. For the left hand side let $k-1$ denote the sum of the first $k$ numbers. Then this partitions the set. The number of ways to get the sum of the first $k$ terms to be $k-1$ is $\binom{2k-2}{k-1}$ then you just count how many ways we can sum the remaining $n-k$ terms to get $n-k$. Which is just $\binom{2n-2k+1}{n-k}$.

I'm missing the $\tfrac{1}{k}$. Also another problem that I found in this arguement is that if I force the first $k$ terms to add up to $k-1$, one of them must be zero. Which then means that I didn't count all of them. Even though i'm way over already.

2) I've tried counting lattice paths from $(0,0)$ to $(n-1,n+1)$, $01$ strings of length $2n$ with exactly $n-1$ $1$'s and picking $n-1$ objects from $2n$ but none of those got both of the binomial coefficients on the LHS.

A hint of what set to count or how to correctly partition one of the sets I've tried would be nice. Thanks


1 Answer 1


One way to do it is to notice that $\frac1k\binom{2k-2}{k-1}=C_{k-1}$, the $(k-1)$-st Catalan number. Among other things, $C_n$ is the number of paths in the plane from from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that take only unit steps to the right or up and never rise above the line $y=x$. (There’s a proof of this at the link.) The plain binomial coefficient $\binom{n}k$ counts the paths from $\langle 0,0\rangle$ to $\langle k,n-k\rangle$ using only unit steps to the right or up: such a path consists of $k$ steps to the right and $n-k$ steps up, any sequence of those steps gets you to $\langle k,n-k\rangle$, and there are $\binom{n}k$ ways to choose where in the sequence of $n$ steps to go to the right.

Thus, $\binom{2n}{n-1}$ counts the paths from the origin to $\langle n-1,n+1\rangle$. The $k$ term of the sum on the left is $C_{k-1}\binom{2n-2k+1}{n-k}$; $C_{k-1}$ counts the paths from the origin to $\langle k-1,k-1\rangle$ that do not rise above the diagonal $y=x$, and $\binom{2n-2n+1}{n-k}$ counts the paths from the origin to $\langle n-k,n-k+1\rangle$ and therefore also the paths from $\langle k-1,k-1\rangle$ to ... what?

Can you finish putting the pieces together?

  • $\begingroup$ Thanks. Took me a while to find out where the extra one came from but it worked out. $\endgroup$ Sep 18, 2013 at 1:24
  • $\begingroup$ Ok, I thought I had it but I was incorrect. This is my argument so far. Maybe you can tell me where I've gone wrong. Let $k-1$ be the first time that the path returns to the line $y=x$. Then $C_{k-1}$ counts half of these paths to $(k-1,k-1)$. Since we can always be above or below the line. Then the remaining $\binom{2n-2k+1}{n-k}$ counts the paths from $(k-1,k-1)$ to $(n-1,n)$. I'm short on because $\binom{2n}{n-1}$ counts the number pf lattice paths from $(0,0)$ to $(n-1,n+1)$. $\endgroup$ Sep 18, 2013 at 1:39
  • $\begingroup$ @user90401 Remember that you need to define the bijection between sets. The 'RHS' is obvious, so think about how to map the LHS to that set. $\endgroup$
    – Calvin Lin
    Sep 18, 2013 at 1:51
  • $\begingroup$ @user90401: The origin is on $y=x$, and the endpoint $\langle n-1,2n\rangle$ is above it, so every path from the origin to $\langle n-1,2n\rangle$ must rise above the diagonal at some point. Say it first so at $\langle k-1,k\rangle$; then it can be broken into a path from the origin to $\langle k-1,k-1\rangle$ and ... ? $\endgroup$ Sep 18, 2013 at 2:05
  • $\begingroup$ I don't know where we are getting $(n-1,2n)$. That is way more steps than $\binom{2n}{n-1}$. $\endgroup$ Sep 18, 2013 at 2:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .