Math CentralQuandaries & Queries


Question from Bristal:

Prove, nC0 + nC1 + nC2 + .... + nCn = 2^n.

Hi Bristal,

Suppose $S$ is a set with $n$ elements and $0 \le r \le n.$ The number $_{n}C_{r}$ is the number of ways of choosing $r$ item from $n$ items or, in other words, the number of subsets of $r$ elements from $S.$ Hence

\[_{n}C_{0} + _{n}C_{1} + _{n}C_{2} + \cdot \cdot \cdot + _{n}C_{n}\]

is the number of subsets of $S.$

You can however count the number of subsets of $S$ another way. Suppose you are going to construct the subsets of $S.$ Go through the $n$ elements of $S,$ one at a time and decide if you are going to include that element in your subset or not. For the first element you consider you can start 2 subsets, one that includes this element and one that does not. For each of the subsets you have started consider the second element. You can include it or not and hence each subset you started expands to 2 subsets and hence you have $2 \times 2 = 2^2$ subsets started. Continue to look at the remaining elements of $S$ and yo will see that you have constructed $2^n$ subsets. Hence there are $2^n$ subsets of $S.$

I hope this helps,

About Math Central
* Registered trade mark of Imperial Oil Limited. Used under license.


Math Central is supported by the University of Regina and the Imperial Oil Foundation.
Quandaries & Queries page Home page University of Regina Imperial Oil Foundation