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

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

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

• Nice answer (+1). – Markus Scheuer Mar 26 at 20:04