Why each row of Pascal's triangle adds up to 2ⁿ
Need a hint?
Count subsets by their size, and also by deciding yes or no for each element.
A 5-element set has 2⁵ = 32 subsets, and the entries of row 5 of Pascal's triangle (1, 5, 10, 10, 5, 1) add up to 32.
How to work it out
A subset of a 5-element set is a yes/no choice for each element: subsets.
Counting by size: is row 5 of Pascal's triangle, and
(1)
LaTeX source of the formulas on this page
\[ 2^5=32 \] \[ 1+5+10+10+5+1=32=2^5 \]
Questions
What is the answer to: Why each row of Pascal's triangle adds up to 2ⁿ?
A 5-element set has 2⁵ = 32 subsets, and the entries of row 5 of Pascal's triangle (1, 5, 10, 10, 5, 1) add up to 32.
What is the key idea?
Count the same set of subsets in two ways: by size and by independent choices.
Is there a hint?
Count subsets by their size, and also by deciding yes or no for each element.