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

Question

Give combinatorial proof for:

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

RHS: We want to make sequence A and B with their element only 0 and 1, and the number of element 1 is k in A and B. From sequence A, pick one element 1, and that number colored by red.

LHS: Try to counting that sequence A and B with another way. I'm trying to consider element 1 k-th position. So this element can be in k,k+1,...,n-1,n in sequence

Answer 1

$k\binom{n}k^2$ counts the number of ways to select two subsets $A$ and $B$ of $\{1,2,\dots,n\}$, and then select a special element of $A$.

How many ways are there to do this so the maximum element of $A\cup B$ is $i$? There are three cases:

• If $\max A=\max B$, then the remaining $k-1$ elements of $A$ and $B$ can be freely chosen in $\binom{i-1}{k-1}^2$ ways.

• If $\max A>\max B$, then $A$'s other elements can be chosen in $\binom{i-1}{k-1}$ ways, and all of $B$'s elements can be chosen in $\binom{i-1}k$ ways, for a total of $\binom{i-1}{k-1}\binom{i-1}k$.

• If $\max A<\max B$, the number of ways to choose $A$ and $B$ is still $\binom{i-1}{k-1}\binom{i-1}k$.

Finally, we must multiply by $k$ to account for choosing the special element of $A$. The result is

$$ k\left(\binom{i-1}{k-1}^2+2\binom{i-1}{k-1}\binom{i-1}k\right) $$ This simplifies to $(2i-k)\binom{i-1}{k-1}^2$.