Exercise 1608Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Another double count

#double counting#combinatorial identity#binomial

Statement

Prove that $\sum_{k=0}^n k\binom{n}{k}=n\cdot2^{n-1}$ by double counting.

Hint

Count pairs $(S,x)$ with $x\in S\subseteq\{1,\ldots,n\}$ .

Show solutionHide solution

First count. Fix $x$ : $x$ belongs to $2^{n-1}$ subsets. Sum over $n$ elements: $n\cdot2^{n-1}$ .

Second count. Fix subset size $k$ : $\binom{n}{k}$ subsets, each with $k$ elements, so $k\binom{n}{k}$ pairs. Sum: $\sum_k k\binom{n}{k}$ .

Conclusion. Both equal the number of pairs, so $\sum_k k\binom{n}{k}=n\cdot2^{n-1}$ .