Exercise 1530Combinatorics › Binomial coefficientsL1Added 3 Nov 2026

Choosing subsets of subsets

#subsets#binomial#identity

Statement

Show that $\sum_{k=0}^{n}\binom{n}{k}2^k=3^n$ .

Hint

Binomial theorem with $a=1$ , $b=2$ .

Show solutionHide solution

Solution

Binomial. $(1+2)^n=\sum_k\binom{n}{k}2^k=3^n$ .

Conclusion. The identity holds.

Combinatorial. Color each element with $3$ colors: $3^n$ colorings. Classify by number $k$ of non-zero elements: $\binom{n}{k}2^k$ (choose $k$ non-zero positions, $2$ colors each).

Choosing subsets of subsets

Statement

Solution

More problems in Binomial coefficients