A recursion formula related to *Catalan numbers*

378 Views Asked by At

When I was working on a problem related to Catalan Number, I deduced the following recursion formula: \begin{equation} a_{l,r}=a_{l-1,r}+a_{l-1,r-1}+a_{l-1,r-2}+\ldots+a_{l-1,l-1},\\ where \quad r \ge l \ge 1,\\ and \quad a_{1,r}=1. \end{equation} And I used another method to derive that: \begin{equation} a_{l,r}=\binom{l+r-1}{l-1} - \binom{l+r-1}{l-2},r \ge l \ge 1. \end{equation} But I don't know how to deduce the above formula of $a_{l,r}$ by directly using its recursion formula or by using generating function. Any ideas?