I have been able to prove the following using the snake oil method:

$$\sum_{k \ge 0} C_k {{n-2k} \choose {l-k}} = {{n+1} \choose {l}}$$ where $l,n$ are positive integers and $C_k$ is the $k$-th Catalan number.

Question: Can someone please show me the combinatorial proof for the case $l \le n$? Thanks

  • $\begingroup$ I doubt this can be proven combinatorially in the case when $n+1 < 2l$; the binomial coefficients on the left hand side have weird signs in that case. $\endgroup$ – darij grinberg Oct 19 '18 at 3:54
  • $\begingroup$ Here is a hint for a semi-combinatorial proof: In the case when $l \leq n+1-l$, count the lattice paths from $\left(0,0\right)$ to $\left(l,n+1-l\right)$ that consist of horizontal steps ($\left(1,0\right)$) and vertical steps ($\left(0,1\right)$). The right hand side counts these paths in an obvious way. The left hand side counts them by the first time they emerge from below the $x=y$ diagonal (i.e., the first vertical step of the form $\left(k,k\right) \to \left(k,k+1\right)$). Of course, this first time is only guaranteed to exist if $l \leq n+1-l$. Handle the ... $\endgroup$ – darij grinberg Oct 19 '18 at 3:56
  • $\begingroup$ ... general case by arguing that both sides are polynomials in $n$ (assuming that the sum on the left hand side ends at $k=l$). $\endgroup$ – darij grinberg Oct 19 '18 at 3:56

Your Answer

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

Browse other questions tagged or ask your own question.