Solution to recurrence $c_{l+1,t}=c_{l,t+1}-c_{l-1,t+1}$. I have the following recurrence:
$$c_{l+1,t}=c_{l,t+1}-c_{l-1,t+1}\tag{1}$$
I know the initial conditions:
$$c_{k,t}=0 \;\;\forall \;\; k<0$$
$$c_{0,t}=\frac{{2t \choose t}}{t+1}$$
I know the solution to the recurrence is:
$$c_{l,t}={2t+l \choose t}\frac{l+1}{t+l+1}$$
How do I get this closed form expression (I can prove it with induction when I know the solution, but how would I have found it)?

My attempt:
Substitute $l=0$ in equation (1).
$$c_{1,t}=c_{0,t+1}$$
Now substitute $l=1$
$$c_{2,t}=c_{0,t+2}-c_{0,t+1}$$
With $l=2$
$$c_{3,t}=c_{0,t+3}-2c_{0,t+2}$$
Going on like this,
$$c_{4,t}=c_{0,t+4}-3c_{0,t+3}+c_{0,t+2}$$
$$c_{5,t}=c_{0,t+5}-4c_{0,t+4}+3c_{0,t+3}$$
$$c_{6,t}=c_{0,t+6}-5c_{0,t+5}+3c_{0,t+4}+2c_{0,t+3}$$
$$c_{7,t}=c_{0,t+7}-6c_{0,t+6}+4c_{0,t+5}+3c_{0,t+4}-c_{0,t+3}$$
I can't see any pattern (apart from $c_{l,t}=c_{0,t+l}-(l-1)c_{0,t+l-1}+<stuff>$) emerging.
 A: There actually is a pattern, though it shows up more clearly after another steps or two: if we ignore the signs, which simply alternate, the coefficients can be read off diagonals in Pascal’s triangle. (I’ve tried to emphasize them by coloring them alternately black and brown.)
$$\newcommand\br{\color{brown}}\begin{array}{cc}
1\\
\br{1}&1\\
1&\br{2}&1\\
\br{1}&3&\br{3}&1\\
1&\br{4}&6&\br{4}&1\\
\br{1}&5&\br{10}&10&\br{5}&1\\
1&\br{6}&15&\br{20}&15&\br{6}&1\\
\br{1}&7&\br{21}&35&\br{35}&21&\br{7}&1\\
\end{array}$$
In other words, it appears that
$$c_{k,t}=\sum_i(-1)^i\binom{k-i}ic_{0,t+k-i}\;;$$
note that $\binom{k-i}i=0$ if $i<0$ or $i>\frac{k}2$. Since $c_{0,t}=C_t$, the $t$-th Catalan number, we can rewrite this as
$$c_{k,t}=\sum_i(-1)^i\binom{k-i}iC_{t+k-i}\;.$$
Those diagonals are actually rather interesting:
$$\sum_i\binom{k-i}i=F_{k+1}\;,$$
the $(k+1)$-st Fibonacci number, and
$$\sum_i(-1)^i\binom{k-i}i=\begin{cases}
1,&\text{if }k\bmod 6=0\\
1,&\text{if }k\bmod 6=1\\
0,&\text{if }k\bmod 6=2\\
-1,&\text{if }k\bmod 6=3\\
-1,&\text{if }k\bmod 6=4\\
0,&\text{if }k\bmod 6=5\;.
\end{cases}$$
(For the latter see this question and answer.)
I’m not sure, however, that this really gets you much further.
Another approach is to start with the generating function $c(x)$ for the Catalan numbers; it’s well-known that it satisfies the equation $c(x)=x\big(c(x)\big)^2+1$, which I will rewrite as $x\big(c(x)\big)^2=xc(x)-1$. From this it follows immediately that
$$x\big(c(x)\big)^{k+2}=\big(c(x)\big)^{k+1}-\big(c(x)\big)^k$$
for $k\ge 0$. This looks very much like your recurrence, the extra factor of $x$ on the lefthand side corresponding to the offset in $t$ in the recurrence. This suggests that we’re looking at repeated convolutions of the Catalan numbers, and so we are: a generalization of these numbers is treated in Example $\mathbf{5}$ in Section $7.5$ of Graham, Knuth, & Patashnik, Concrete Mathematics. After getting the notation properly matched up, we find that
$$c_{\ell,t}=\binom{2t+\ell+1}t\frac{\ell+1}{2n+\ell+1}=\binom{2t+\ell}t\frac{\ell+1}{t+\ell+1}\;.$$
This PDF is also helpful. This PDF on the Catalan transform is also relevant: Problem $\mathbf{1}$ shows how it generates your numbers $c_{2,t}$. This one discusses the Catalan transform in more detail.
