Combinatorial proof for $\sum_{i=r}^{n}(2i-r)\binom{i-1}{r-1}^2=r\binom{n}{r}^2$

Question

I was wondering if we could combinatorially interprete the following identity

$$\sum_{i=r}^{n}(2i-r)\binom{i-1}{r-1}^2=r\binom{n}{r}^2$$

Answer 1

As usual let $[n]=\{1,\ldots,n\}$. Let $[n]^r$ be the family of $r$-subsets of $[n]$. Then $r\binom{n}r^2$ is the cardinality of

$$\mathscr{T}=\{\langle A,B,i\rangle\in[n]^r\times[n]^r\times[n]:i\in A\}\;.$$

That is, it’s the number of ways to choose two $r$-subsets of $[n]$, $A$ and $B$, and then to single out a specific element of $A$, the first $r$-subset.

For $\langle A,B,i\rangle\in\mathscr{T}$ let $m_{\langle A,B,i\rangle}=\max(A\cup B)$; clearly $r\le m_{\langle A,B,i\rangle}\le n$. For $k=0,\ldots,n-r$ let

$$\mathscr{T}_k=\{T\in\mathscr{T}:m_T=r+k\}\;.$$

Say that $T=\langle A,B,i\rangle\in\mathscr{T}_k$. If $m_T=\max A$, there are $\binom{r+k-1}{r-1}$ ways to choose the rest of $A$, $\binom{r+k}r$ ways to choose $B$, and $r$ ways to choose $i$, for a total of

$$r\binom{r+k}r\binom{r+k-1}{r-1}=r\cdot\frac{r+k}r\binom{r+k-1}{r-1}^2=(r+k)\binom{r+k-1}{r-1}^2$$

possibilities. There are just as many possibilities with $m_T=\max B$. However, that double counts the case in which $\max A=\max B$, which can be chosen in $$r\binom{r+k-1}{r-1}^2$$ ways. The grand total is therefore

$$\begin{align*} |\mathscr{T}_k|&=2(r+k)\binom{r+k-1}{r-1}^2-r\binom{r+k-1}{r-1}^2\\\\ &=\big(2(r+k)-r\big)\binom{r+k-1}{r-1}^2\\\\ &=(2i-r)\binom{i-1}{r-1}^2\;, \end{align*}$$

where $i=r+k$. Thus,

$$r\binom{n}r^2=|\mathscr{T}|=\sum_{k=0}^{n-r}|\mathscr{T}_k|=\sum_{k=0}^{n-r}\big(2(r+k)-r\big)\binom{r+i-1}{r-1}^2=\sum_{i=r}^n(2i-r)\binom{i-1}{r-1}^2\;.$$