What is the proof that the total number of subsets of a set is $2^n$? What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
 A: Suppose you want to choose a subset. For each element, you have two choices: either you put it in your subset, or you don't; and these choices are all independent.
Remark: this works also for the empty set. An empty set has exactly one subset, namely the empty set. And the fact that $2^0=1$ reflects the fact that there is only one way to pick no elements at all!
A: Here is proof by binary numbers. A set of up to N items can be represented as a vector of binary digits. When a digit is 1, it indicates that the corresponding item is present. 0 means that it is absent. 
In fact, this representation is used in computer programming as a way of representing sets which has good worst-case memory efficiency, as well as other attributes such as simplicity of implementation.
So for instance a set of 32 items can be represented as a string of 32 1's.  And then we can represent subsets of these items, by flipping some of these 1's to 0's in various combinations.
All possible subsets are therefore, simply, all possible 32 bit numbers, and there are $2^{32}$ such numbers.
In other words, the count of subsets is related to the fact that set membership is a binary proposition: something is or is not an element of a set. Yes or no, true or false, one or zero.
A: Here is a proof by induction on $n$.  This proof assumes that we have defined $2^n$ by recursion as $2^0 = 1$ and $2^{n+1} = 2^n \cdot 2$.
This is true for $n=0$ because $\emptyset$ has exactly one subset, namely $\emptyset$ itself.
Now assume that the claim is true for sets with $n$ many elements. Given a set $Y$ with $n+1$ many elements, we can write $Y = X \cup \{p\}$ where $X$ is a set with $n$ many elements and $p \notin X$.  There are $2^n$ many subsets $A \subset X$, and each subset $A \subset X$ gives rise to two subsets of $Y$, namely $A \cup \{p\}$ and $A$ itself.  Moreover, every subset of $Y$ arises in this manner.  Therefore the number of subsets of $Y$ is equal to $2^n \cdot 2$, which in turn is equal to $2^{n+1}$.
A: We must show that $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$$ is the number of subsets of an $n$-element set $S$ where $n\geq0$.
Every subset of $S$ is a $k$-subset of $S$ where $k=0,1,2,...,n$. We know that ${n\choose k}$ equals the number of $k$-subsets of S. Thus by the Addition Principle $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}$$ equals the number of subsets to the set $S$. We can count the same thing by observing that each element of the set $S$ has two choices, either they are in a subset or they are not in a subset. Let $S=\{x_1,x_2,x_3,...,x_n\}$. So, $x_1$ is either in a subset or it is not in a subset, $x_2$ is either in a subset or it is not in a subset,..., $x_n$ is either in a subset or it is not in a subset. Thus by the Multiplication Principle there are $2^n$ ways we can form a subset of the set $S$. Hence ${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$.
Another approach is to consider the Binomial Theorem $$(x+y)^n=\sum_{k=0}^n {n\choose k}x^{n-k}y^k.$$ Letting $x=1$ and $y=1$ we obtain$$2^n=\sum_{k=0}^n{n\choose k}.$$
A: If $S$ is a finite set with $|S| = n$ elements, then the number of subsets of $S$ is $|\mathcal{P}(S)| = 2^n$. This fact, which is the motivation for the notation $2^S$, may be demonstrated as follows,
We write any subset of $S$ in the format $\{x_1, x_2, \ldots, x_n\}$ where $x_i , 1 \le i \le n$, can take the value of $0$ or $1$. If $x_i = 1$, the $i$-th element of $S$ is in the subset while the $i$-th element is not in the subset otherwise. Clearly the number of distinct subsets that can be constructed this way is $2^n$.
A: \begin{align}
  \sum_{k=0}^n{n \choose k}=2^n
\end{align}
can be solved using proof by induction.
for $n=1$;
it is true (put n=1);
for $n=k$;
assume to be true.
\begin{align}
     \sum_{k=0}^n{n \choose k}=2^n
   \end{align}
for $k=n+1$;
\begin{align}
   \sum_{k=0}^{n+1}{n+1 \choose k}=2^{n+1}\end{align}
\begin{align}
{n+1 \choose k}={n \choose k}+{n \choose k-1}
\end{align}
substituting this equation leads to the final result.
A: To write out some details of the discussion under this answer. Consider the two element set $\{0,1\}$ where you think of $1$ as meaning in the subset and $0$ as meaning not in the subset. In this way any function $f\colon S \to \{0,1\}$ defines a subset of $S$, where $s$ is in that subset if and only if $f(s)=1$. So then our question is how many such functions are there? For each of the $n$ elements of $S$ there are two choices for what $f(n)$ can be, so making these $n$ choices independently, there are $2^n$ options.
A: Here's a combinatoral proof
$$\sum_{k=0}^n{n \choose k}=2^n$$
These both count the number subsets in an $n$ element set.
The right hand side counts them directly (related to Marie's answer) and the left hand side counts the number of $k$-element subsets and then sums over $k$. This equation can also be verified by the binomial theorem with $x=y=1$.
A: Let us consider the following cases: 


*

*Let a set be $\{a\}$, then its subsets are: $\{a\}, {\emptyset}$ . Therefore the number of subsets is $2^1$

*Let another set be $\{a,b\}$, then its subsets are: $\{a\},\{b\},\{a,b\}, {\emptyset}$ Therefore the number of subsets is $2^2$

*Let another set be $\{a,b,c\}$, then its subsets are: $\{a\},\{b\},\{c\},\{a,b,c\},\{a,b\},\{b,c\},\{a,c\}, {\emptyset}$. Therefore, the number of subsets is $2^3$
$\therefore$  (1), (2) & (3) $\Rightarrow $ If there are $n$ sets, then the number of subsets is $2^n$
