# 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.

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

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.