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

Question

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)!}$

Answer 1

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.

Answer 2

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.

Answer 3

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 $

Answer 4

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...

Answer 5

Do you know this is just the binomial formula? It states \begin{equation} (a+b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n-k} \end{equation} Take $a=b=1$ to get your formula.