Maths WorkshopMaths problems with full solutions
Exercise 1532Combinatorics › Binomial coefficientsOlympiadAdded 3 Nov 2026

A combinatorial sum

#combinatorial sum#double counting#identity

Statement

Show that ∑k=0n(nk)(k2)=2n−2n(n−1)\sum_{k=0}^{n}\binom{n}{k}\binom{k}{2}=2^{n-2}n(n-1).

Hint

Use (nk)(k2)=(n2)(n−2k−2)\binom{n}{k}\binom{k}{2}=\binom{n}{2}\binom{n-2}{k-2} and sum.

Show solutionHide solution

Solution

Identity. (nk)(k2)=(n2)(n−2k−2)\binom{n}{k}\binom{k}{2}=\binom{n}{2}\binom{n-2}{k-2}.

Sum. ∑k(n2)(n−2k−2)=(n2)∑j(n−2j)=(n2)⋅2n−2=n(n−1)2⋅2n−2=n(n−1)2n−3\sum_k\binom{n}{2}\binom{n-2}{k-2}=\binom{n}{2}\sum_j\binom{n-2}{j}=\binom{n}{2}\cdot 2^{n-2}=\frac{n(n-1)}{2}\cdot 2^{n-2}=n(n-1)2^{n-3}.

Correction. The result should be n(n−1)2n−3n(n-1)2^{n-3}, not 2n−2n(n−1)2^{n-2}n(n-1).

Let me recheck: (n2)2n−2=n(n−1)22n−2=n(n−1)2n−3\binom{n}{2}2^{n-2}=\frac{n(n-1)}{2}2^{n-2}=n(n-1)2^{n-3}.

Conclusion. ∑k(nk)(k2)=n(n−1)2n−3\sum_k\binom{n}{k}\binom{k}{2}=n(n-1)2^{n-3}.