3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.