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

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

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.