Finding the generating polynomial for this string-counting combinatorial identity

Question

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.

Answer 1

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}.} $$

Answer 2

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.