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