Combinations formula shorthand with $2$ as the base.

Question

Hope you are doing great. I hope you will help me to understand one thing related to combinations.

I have grasped general ideas behind permutation and combination, but I can not understand how the specified combinations have been compressed just to $2^{100}-1$ in the following extraction from an online presentation.

$$\binom{100}{1} + \binom{100}{2} + \binom{100}{3} + \cdots + \binom{100}{100} = 2^{100} - 1$$

I had checked whether this formula would work with another case, more simple and it has worked.
I took the case with A,B,C and calculated all possible combinations(A,B,C,AB,AC,ABC,BC) with general combination formula. Below screenshot is represented.

$$\frac{3!}{(3 - 1)!1!} + \frac{3!}{(3 - 2)!2!} + \frac{3!}{(3 - 3)!3!} = 7$$

So the answer is $7$. However, if I use the formula mentioned above and plug numbers $2^3-1$ the answer is also $7$.

I can not understand how this formula was derived and why $2$ is the base? I would appreciate if you help me to figure it out.

Thank you all in advance and sorry if the format is not so straightforward.
Asking questions here is new to me.

Answer 1

Assume that you have a set $S$ with $n$ elements. Your combinations correspond to the (non-empty) subsets of $S$. To construct such a subset, for each of the $n$ elements you must decide whether it is to be contained in your subset or not. So, for each of the $n$ elements, you have $2$ possibilities, which makes a total number of $2^n$ possibilities. If your subset must not be the empty set, you have to subtract $1$ from that number.

Answer 2

First, congrats on stumbling onto an interesting mathematical fact.

A set of $n$ elements has $2^n$ subsets. You can see this by considering the set of all functions from the set to the two element set $\{0,1\}$. Each such function specifies a subset $S$ by defining $S=\{x\mid f(x)=1\}$.

The set of such functions, denoted $Y^X$, where $X$ is the $n$-element set and $Y$ the two-element set, indeed has order $\mid Y^X\mid=\mid Y\mid^{\mid X\mid}=2^n$.

The $-1$ comes because the empty set is not included.

Note, the binomial theorem also gives the result, quite beautifully, by considering $(1+1)^n=\sum_{k=0}^n {n\choose k}$.