By the binomial theorem, use this result to show with explanation that the number of subsets of a set $S$ is $2^{|S|}$

Question

Given that $(1+1)^n = 2^n = \sum^n_{k=0} \binom{n}{k}$ by the binomial theorem use this result to show with explanation that the number of subsets of a set $S$ is $2^{|S|}$

I'm really confused.

So using the formula I got

$(1+1)^s = 2^s = \sum^s_{k=0} \binom{s}{k} 1^{s-0} * 1^0$

= $2^s = \sum^s_{k=0} \binom{s}{k}$

but now what? Any help would be great

Answer 1

Now the following: ${s \choose k}$ is the count of the sub-sets with exactly k elements. When you sum these counts you get the count of all sub-sets. And you just proved that sum is $2^s$.

Answer 2

The number of subsets is $2^S$ because, you either choose an element to be part of it or not, and you do this $S$ times, with each element: $2*... * 2$ (S times) = $2^S$. Multilpying can be done, since you do them independently.