3
$\begingroup$

Consider the following identity $$\sum_{n=0}^{R-t}\binom{n+\ell}n\binom{R-\ell-n}{R-t-n}=\binom{R+1}{t+1}.\tag1$$ It is relatively easy to give an algebraic or mechanical proof of (1). But, I like to ask:

QUESTION. is there a combinatorial reason why the sum in (1) is independent of $\ell$?

$\endgroup$
  • 2
    $\begingroup$ This is ('negative') Chu-Vandermonde, as the LHS is $(-1)^{R-t} \sum_n \binom{-\ell -1}{n}\binom{\ell-t-1}{R-t-n} =(-1)^{R-t} \binom{-t-2}{R-t}=\binom{R+1}{t+1}$. $\endgroup$ – Ofir Gorodetsky Dec 3 '20 at 17:35
3
$\begingroup$

(I am late to post a very similar answer to the already given one, yet I'd like to post it as well, since it differs in some detail)

Changing the summation index to $m=n+\ell$, the identity writes $$\sum_{m=\ell}^{R-t+\ell } {m\choose \ell}{R-m\choose t-\ell}={R+1\choose t+1}.$$

Given natural numbers $\ell\le t\le R$, and $m$, we may consider the class of those $(t+1)$-subsets $\{x_0<x_1<\dots<x_t\}$ of $\{0,1,\dots,R\}$ such that $x_\ell=m$: these are exactly ${m\choose \ell}{R-m\choose t-\ell}$ (indeed the $\ell$ elements $x_0,\dots, x_{\ell-1}$ can be chosen freely into $\{0,\dots, m-1\}$, and so can the $t-\ell$ elements $x_{\ell+1},\dots,x_t$ into $\{m+1,\dots,R\}$. These classes, for $ \ell\le m\le R-t+\ell $ form a partition of all $(t+1)$-subsets of $[R+1]$, whence the sum of their cardinality is independent of $\ell$ and the identity.

$\endgroup$
6
$\begingroup$

Well, here's a combinatorial proof of the identity anyway (but not a direct proof of independence of $\ell$).

Write $N = R - t$. Then the identity is $$\sum_{n=0}^N \binom{n + \ell}{n} \binom{R - n-\ell}{N - n} = \binom{R + 1}{N}.$$ The RHS is the number of $N$-sets $\{x_1 < \cdots < x_N\} \subset \{1, \dots, R+1\}$. Consider the last index $n$ such that $x_n \leq n + \ell$ (say $n = 0$ if there is no such index). Then $\{x_1 < \cdots < x_n\} \subset \{1, \dots, n+\ell\}$ and $\{x_{n+1} < \cdots < x_N\} \subset \{n+\ell+1, \dots, R+1\}$. The number of ways of making these choices is the LHS.

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