How to prove that $\sum_{i=1}^{n} \frac{n!}{i!(n-i)!} = 2^{n} - 1 $ I ran across that problem trying to count how many intersections of sets could be if none of them is a subset another.
If I have a set of sets X={A,B,C}, I have 4 combinations of intersections: $A \cap B, A \cap C, B \cap C, A \cap B \cap C, .. $  I also add $\overline{A}, \overline{B}, \overline{C},$ that means $\overline{A} = A - (B+C)$ I needed it for my own task. Having used combinatorics I have founded the series $C^n_1 + C^n_2 + C^n_3 + ... + C^n_n$. Here I didn't distinguish $A$ and $\overline{A}$. So I got the solution:
$$ \sum_{i=1}^{n} \frac{n!}{i!(n-i)!} $$
Then I noticed that I didn't need combinatorics at all because I have binary code without zero:
C B A
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

So the number of combinations is $2^{n} - 1$. But now I can't figure out how to get the second solution from the first one using some consequence of mathematical operations.
 A: We can write $$\displaystyle \sum^{n}_{i=0}\binom{n}{i} = \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+.........+\binom{n}{m}$$
$\bf{Combinational\; Proof::}$ Considering a group of $n$ person from which a subgroup of some
person is to be formed. This Subgroup may have $0$ person, $1$ person, $2$ person ans so on.
Thus the number of ways of forming Subgroup is $\displaystyle \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+.........+\binom{n}{m}$
Now all these are covered if we note that each person can be in $2$ ways, He is either in the group
or not in the group which will form $2^{n}$ Selections
Thus $$\displaystyle \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+.........+\binom{n}{m} = 2^{n}.$$
So we get $$\displaystyle \binom{n}{1}+\binom{n}{2}+.........+\binom{n}{m} = 2^{n}-\binom{n}{0}=2^n-1.$$
A: Use the Binomial theorem.
$$\sum_{i=0}^n {n \choose i} = \sum_{i=0}^n {n \choose i} 1^i 1^{n-i} = 2^n$$
Now subtract the $i=0$ term.
A: From the Binomial Theorem
$$(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^ky^{n-k}$$
For $x=1$ and $y=1$ we have
$$(1+1)^n=\sum_{k=0}^n\binom{n}{k}1^k1^{n-k}$$
whence we obtain
$$2^n=\sum_{k=0}^n\binom{n}{k}$$
Since $\binom{n}{0}=1$ we arrive at the desired result
$$\sum_{k=1}^n\binom{n}{k}=2^n-1$$
