Maths WorkshopMaths problems with full solutions
Exercise 987Combinatorics › Inclusion-exclusionOlympiadAdded 3 Nov 2026

Binomial identity via IE

#IE#binomial#identity

Statement

Show ∑k=0n(−1)k(nk)=0\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0 for n≥1n\ge1 using IE.

Hint

IE on empty subsets.

Show solutionHide solution

Solution

Universe. All subsets of {1,…,n}\{1,\ldots,n\}.

Sets AiA_i = subsets containing ii. We want subsets with no element, i.e. ∅\varnothing.

IE. ∣∅∣=2n−∑i∣Ai∣+∑i<j∣Ai∩Aj∣−⋯|\varnothing|=2^n-\sum_i|A_i|+\sum_{i<j}|A_i\cap A_j|-\cdots

=2n−n⋅2n−1+(n2)2n−2−⋯=∑k(−1)k(nk)2n−k=2^n-n\cdot2^{n-1}+\binom{n}{2}2^{n-2}-\cdots=\sum_k(-1)^k\binom{n}{k}2^{n-k}.

Setting this equal to 11 (the empty set count) and dividing: ∑k(−1)k(nk)2−k=2−n\sum_k(-1)^k\binom{n}{k}2^{-k}=2^{-n}, so multiplying by 2n2^n: ∑k(−1)k(nk)2n−k=1\sum_k(-1)^k\binom{n}{k}2^{n-k}=1, i.e. ∑k(−1)k(nk)=0\sum_k(-1)^k\binom{n}{k}=0.

Conclusion. The identity holds.