# Proving the total number of subsets of S is equal to $2^n$

Student here! Just reading Liebecks Introduction to pure mathematics for fun and I made an attempt at proving the total number of subsets of S is equal to $2^n$.

I realized that the total number of subsets of S is just:

$\binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} + 1$

And so I put together the cool looking formula

$\displaystyle \sum_{r=1}^n \frac{n!}{r!(n-r)!} = 2^n – 1$

But I have no clue how to approach proving this formula analytically. Any help?

So if I try a proof by induction:

$\displaystyle \sum_{r=1}^n \frac{n!}{r!(n-r)!} = 2^n – 1$

$\displaystyle \sum_{r=0}^n \frac{n!}{r!(n-r)!} = 2^n$

obviously true for $n = 1$:

$1 + \frac{1}{1!0!} = 2 = 2$

assume true for $n$, I could multiply both sides by $2$?

$\displaystyle 2\sum_{r=0}^n \frac{n!}{r!(n-r)!} = 2^{n+1}$

How could I go about proving that

$\displaystyle 2\sum_{r=0}^n \frac{n!}{r!(n-r)!} = \sum_{r=0}^{n+1} \frac{(n+1)!}{r!((n+1) – r)!}$

#### Solutions Collecting From Web of "Proving the total number of subsets of S is equal to $2^n$"

You can prove it by induction.

First off start by noticing that $$\displaystyle \sum_{r=1}^n \frac{n!}{r!(n-r)!} = 2^n – 1\iff \displaystyle \sum_{r=0}^n \overbrace{\frac{n!}{r!(n-r)!}}^{\displaystyle \binom{n}{r}} = 2^n$$

Due to the equivalence above, it suffices to prove that $\displaystyle \sum_{r=0}^n \binom{n}{r} = 2^n$. (The only reason I chose to prove this one instead is because I feel it is more aesthetically pleasing).

Base case: $n=0$

$\displaystyle \sum_{r=0}^0 \binom{0}{r} = \displaystyle \sum_{r=0}^0 \frac{0!}{r!(0-r)!} = \frac{0!}{0!0!}=1=2^0$

Induction step: Let $n\in \Bbb N$ and suppose $\displaystyle \sum_{r=0}^n \binom{n}{r} = 2^n$. Multiply by $2$ to get: $$\displaystyle 2\sum_{r=0}^n \binom{n}{r} = 2^{n+1}.$$

Also that is left is to prove that $\displaystyle 2\sum_{r=0}^n \binom{n}{r}=\sum_{r=0}^{n +1}\binom{n+1}{r}$. The green equality below is a consequence of Pascal’s rule:

\begin{align} 2\sum_{r=0}^n \binom{n}{r}&=\sum_{r=0}^n \binom{n}{r}+\sum_{r=0}^n \binom{n}{r}\\ &=\binom{n}{0}+\sum_{\color{red}{r=1}}^n \binom{n}{r}+\sum_{r=0}^{\color{blue}{n-1}} \binom{n}{r}+\binom{n}{n}\\ &=1+\sum_{\color{red}{r=0}}^\color{red}{n-1} \binom{n}{\color{red}{r+1}}+\sum_{r=0}^{{n-1}} \binom{n}{r}+1\\ &=1+\sum _{r=0}^{n-1}\left[\binom{n}{r+1}+\binom{n}{r}\right]+1\\ &\color{green}=1+\sum_{r=0}^{n-1} \binom{n+1}{r+1} + 1\\ &=\binom{n+1}{0}+\sum _{\color{red}{r=1}}^\color{red}n\binom{n+1}{\color{red}r}+\binom{n+1}{n+1}\\ &=\binom{n+1}{0}+\sum _{r=1}^{n+1}\binom{n+1}{r}\\ &=\sum _{r=0}^{n+1}\binom{n+1}{r} \end{align}

Note that starting on the third line I use $n-1$. This is only correct if $n\ge 1$, but if $n=0$, it’s just the base case.

I just noticed that your base case is for $n=1$, that’s fine. Mine is a bit more general.

Hint: To form a subset, for each element of $S$ we have to decide whether to include or to exclude that element. If $|S| = n$, $n$ decisions must be made.

This can be proved by simple approach as :
Suppose S is $S = \lbrace a_1,a_2,a_3,………….a_n \rbrace$
For subset a element can be selected in 2 way,either it is selected or not selected.
So total subset is :

$\lbrace 2.2.2.2…………2\rbrace$ \\ n times multiplication of 2

$= 2^n$

Let the statement be denoted by P(N) Case N=0… Clearly a set with no elements is Null set…(Phi) there fore has only Null set as its subset. As 2^0 is 1… P(0) is correct.

Case N=1… Clearly a set with 1 element has only 2 subsets,that and null set. As 2^1 is 2… P(1) is correct.

Now suppose P(x) is true where x is a Natural number. ie a set having x no. of elements has 2^x subsets.

we have to prove that P(x+1) is true. ie, a set having x+1 elements has 2^(x+1) subsets. In this set we have n1,n2….nx and then nx+1 newly added apart from the subsets that can be formed with n1,n2…nx… we can form additional subsets by choosing any number from 1 to x among n1,n2…nx… ie,xC0+xC1+…. xC = 2^x (xC0 for a set with nx+1 alone). Now trying to account for a total it becomes 2^x+2^x = 2*2^x = 2^(x+1)

Thus by principle of induction P(x) is true for all x=0,1,2…

Do you know this is just the binomial formula? It states

(a+b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n-k}

Take $a=b=1$ to get your formula.