WordGPT

Why each row of Pascal's triangle adds up to 2ⁿ

Exercise · Level 2 (Easy)

How many subsets does a set with 5 elements have, and how does that relate to row 5 of Pascal's triangle?

(n0)+(n1)+⋯+(nn)=2n\binom n0+\binom n1+\cdots+\binom nn=2^n

wordgptpro.com

Solution

  1. A subset of a 5-element set is a yes/no choice for each element: 2⋅2⋅2⋅2⋅2=25=322\cdot2\cdot2\cdot2\cdot2=2^5=32 subsets.

  2. Counting by size: (50)=1, (51)=5, (52)=10, (53)=10, (54)=5, (55)=1\binom50=1,\ \binom51=5,\ \binom52=10,\ \binom53=10,\ \binom54=5,\ \binom55=1 is row 5 of Pascal's triangle, and

    1+5+10+10+5+1=32=25\begin{aligned}&1+5+10+10+5+1\\&=32=2^5\end{aligned}
    (1)
Answer25=322^5=32

wordgptpro.com

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

  1. A subset of a 5-element set is a yes/no choice for each element: 2⋅2⋅2⋅2⋅2=25=322\cdot2\cdot2\cdot2\cdot2=2^5=32 subsets.

  2. Counting by size: (50)=1, (51)=5, (52)=10, (53)=10, (54)=5, (55)=1\binom50=1,\ \binom51=5,\ \binom52=10,\ \binom53=10,\ \binom54=5,\ \binom55=1 is row 5 of Pascal's triangle, and

    1+5+10+10+5+1=32=25\begin{aligned}&1+5+10+10+5+1\\&=32=2^5\end{aligned}
    (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.

Related problems

More probability and puzzles

    Why each row of Pascal's triangle adds up to 2ⁿ: answer and solution | WordGPT