# On the Catalan Numbers

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

• 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. – darij grinberg Oct 19 '18 at 3:54
• 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 ... – darij grinberg Oct 19 '18 at 3:56
• ... general case by arguing that both sides are polynomials in $n$ (assuming that the sum on the left hand side ends at $k=l$). – darij grinberg Oct 19 '18 at 3:56