Finding the generating polynomial for this string-counting combinatorial identity The combinatorial identity goes as follows:
$$ \sum_{k=0}^\ell {n+k-1 \choose k} {n-k-1 \choose {\ell-k}} = {2n-1 \choose \ell } \ ,\ell \leqslant n-1 $$ 
Intuitively, the RHS counts all (0,1)-strings of length $(2n-1)$ which contain $\ell$ 0(s), and a string of this form must contain an $n-$th 1. Classifying the loci of the $n-$th 1 (from $n$ to $n+\ell$) yields the LHS.
However, is there a generating function that generates this identity? I find this intriguing. Thanks a lot if anybody could think about this.
 A: Recall we can extend $\binom{n}k$ to negative $k$ with the convention $\binom{n}k=\frac{n(n-1)\cdots (n-k+1)}{k!}$, in which case we have
$$
\binom{-n}k=(-1)^k\binom{n+k-1}k.
$$
We can use this to write your equation as
$$
\sum_{k=0}^\ell (-1)^k\binom{-n}k\cdot (-1)^{\ell-k}\binom{-n+\ell}{\ell-k}=(-1)^\ell\binom{-2n+\ell}{\ell},\tag{*}
$$
Using Newton's binomial theorem $(1+x)^m=\sum_k \binom{m}k x^k$, valid for all $m\in \mathbb R$, $(*)$ is the $[x^\ell]$ cooeficient of the equation
$$
\boxed{(1-x)^{-n}\cdot (1-x)^{-n+\ell}=(1-x)^{-2n+\ell}.}
$$
A: Using formal power series we find
$$\sum_{k=0}^\ell {n+k-1\choose k} {n-k-1\choose \ell-k}
= \sum_{k=0}^\ell {n+k-1\choose k}
[z^{\ell-k}] (1+z)^{n-k-1}
\\ = [z^{\ell}] (1+z)^{n-1}
\sum_{k=0}^\ell {n+k-1\choose k}
z^k (1+z)^{-k}.$$
Here  we  may  extend  $k$  beyond $\ell$  owing  to  the  coefficient
extractor in front:
$$[z^{\ell}] (1+z)^{n-1}
\sum_{k\ge 0} {n+k-1\choose k}
z^k (1+z)^{-k}
= [z^{\ell}] (1+z)^{n-1}
\frac{1}{(1-z/(1+z))^n}
\\ = [z^{\ell}] (1+z)^{n-1}
\frac{(1+z)^n}{(1+z-z)^n}
= [z^{\ell}] (1+z)^{2n-1}
= {2n-1\choose \ell}.$$
This is the claim. Another approach is
to write using $n-1\ge \ell$:
$$\sum_{k=0}^\ell {n+k-1\choose k} {n-k-1\choose \ell-k}
= \sum_{k=0}^\ell
{n+k-1\choose k} {n-\ell-1+\ell-k\choose \ell-k}
\\ = \sum_{k=0}^\ell
[z^k] \frac{1}{(1-z)^n}
[z^{\ell-k}] \frac{1}{(1-z)^{n-\ell}}
\\ = [z^\ell] \frac{1}{(1-z)^{2n-\ell}}
= {2n-\ell-1+\ell\choose 2n-\ell-1}
\\ = {2n-1\choose 2n-1-\ell}
= {2n-1\choose \ell},$$
and we have the claim once  more. Maybe we will see additional answers
that that make the connection to generating functions more explicit.
