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


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$ – TheNumber23 Sep 18 '13 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$ – TheNumber23 Sep 18 '13 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 '13 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$ – Brian M. Scott Sep 18 '13 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$ – TheNumber23 Sep 18 '13 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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