How to prove the sum of combination is equal to $2^n - 1$

Question

One of the algorithm I learnt involve these steps:

$1$. define a set $S$ of $n$ elements

$2$. form a subset $S'$ of $k$ choice from $n$ elements of the set $S$ ($k$ starts with $1$), which is effectively the combination of $n$ choose $k$: $\frac{n!}{k!(n-k)!}$

$3$. repeat until $k = n$

So for example: $n=5, s = \{A,B,C,D,E\}$

1. 1st round:

   {A},{B},{C},{D},{E}
   
   (k=1 => n!/k!(n-k)! = 5 outcomes)
   

2. 2nd round:

   {A,B}, {A,C}, {A,D}, {A,E}, 
   {B,C}, {B,D}, {B,E}
   {C,D}, {C,E}
   {D,E}
   
   (k = 2 => n!/k!(n-k)! = 10 outcomes)
   

3. 3rd round:

   {A,B,C}, {A,B,D}, {A,B,E}
   {B,C,D}, {B,C,E}
   {C,D,E}, {C,D,A}
   {D,E,A}, {D,E,B}
   
   (k = 3 => n!/k!(n-k)! = 10 outcomes)
   

4. 4th round:

   {A,B,C,D}, {A,B,C,E}
   {B,C,D,E}
   {C,D,B,E}
   {D,C,A,E}
   
   (k = 4 => n!/k!(n-k)! = 5 outcomes)
   

5. 5th round:

   {A,B,C,D,E}
   
   (k = 5 => n!/k!(n-k)! = 1 outcomes)
   

The total outcome $t = 5 + 10 + 10 + 5 + 1 = 31$

Which correspond to the formula $2^n - 1$ (predicted by the algorithm)

So I was trying to prove that the sum of this series will result in $2^n - 1$ but did not succeed

series s

    s = n!/1!(n-1)! + n!/2!(n-2)! + ... + n!/(n-2)(n-(n-2))! + n!/(n-1)(n-(n-1))! + n!/n!(n-n)!

    s = n!/1!(n-1)! + n!/2!(n-2)! + ... + n!/(n-2)2! + n!/(n-1)1! + n!/n!

    s = n!/1!(n-1)! + n!/2!(n-2)! + ... + n!/(n-2)2! + n!/(n-1)1! + 1

could we prove the series above = $2^n - 1$? Or am I on the wrong side of the road?

Answer 1

The binomial theorem states that $$\sum_{k=0}^n \binom{n}{k} x^k=(1+x)^n$$ Putting $x=1$ gives $$\sum_{k=0}^n \binom nk=2^n\\ \sum_{k=1}^n\binom nk=2^n-1$$

Answer 2

Taking all the rounds together (including the $0^{th}$), you have formed all combinations with any of the five letters taken or not, which you can do in $2\cdot2\cdot2\cdot2\cdot2$ ways. (Equivalently, all five bits numbers from $00000$ to $11111$, which is exactly $2^5$.)

For perfect rigor, one should show that there are no repetitions nor omissions.

Answer 3

Let's consider the meaning of $\sum_{k=1}^n \left(\begin{array}{c} n \\ k \end{array} \right).$ You are interested in the number of ways to construct a non-empty subset from the original set of $n$ elements.

Consider the set with $n$ elements, for each element, we have two options, to include it in one of the subset or not. If we allow our subset to be empty, the number of possible subset is $2^n$. To ensure that our subset is non-empty, we exclude the empty set,hence

$$\sum_{k=1}^n \left(\begin{array}{c} n \\ k \end{array} \right)=2^n-1$$