How do I prove a set's power has $2^n$ elements? It seems to have the same behavior as Pascal's pyramid, there's
for a 2 elements set (let's call it A):
$P(A)=\{\{\emptyset \}\{a\}\{b\}\{a,b\}\}$
there is 1 empty set always, 2 sets with 1 single element, and 1 last set (which is always itself)
This seems like a good insight, but i don't feel like this is nowhere formal proof.
 A: Induction.
A 1-element set: $\{a\}$ has 2 subsets: emptyset and itself.
Assume that $n$-element set has $2^n$ subsets.
Take any $(n+1)$-element set $A=\{a_1,\dots,a_n,a_{n+1}\}$.
Let's write $A=B\cup\{a_{n+1}\}$, where $B=\{a_1,\dots,a_n\}$ is a $n$-element set.
Every subset of $A$ is either a subset of $B$ or a subset of $B$ with element $a_{n+1}$ also included.
There are $2^n$ subsets of $B$ by the assumption, so there are  $2^n$ subsets of $A$ without $a_{n+1}$ and $2^n$ subsets of $A$ with $a_{n+1}$ as an element.
Hence there are $2^n+2^n=2^{n+1}$ subsets of $A$.
A: No wonder it's similar to Pascal's triange.
That's because $n \choose k$ is the number of the $k$-element subsets.
So to find the number of all subsets just sum-up   $n \choose k$ over $k=0,1,2,\ldots,n$   
You get:    
$$\sum_{k=0}^n {n \choose k} = (1+1)^n = 2^n$$    
The first $=$ above uses the binomial formula.  
A: Say you have a list of all subsets of the set $\{a,b,c,d,\ldots,w\}$ (where $w$ is of course the ten zillionth letter of the alphabet).  Add just one more item $x$ to your set, getting $\{a,b,c,d,\ldots,w\} \cup \{x\} = \{a,b,c,d,\ldots,w,x\}$.  Then make a new list consisting of $(1)$ the list you've already got, of all subsets of $\{a,b,c,d,\ldots,w\}$, plus $(2)$ the same list with $x$ added as a new member to every set in the list.  You get a list that's twice as long.  Every time you add one new member to your set, the list gets twice as long.
A: Number all the subsets of $A$ with binary numbers of $\#A$ bits, by associating every element to a bit. A $1$ indicates presence of the element. This establishes a bijection between the subsets and the numbers.
$$\{\emptyset\}\leftrightarrow00\\
\{a\}\leftrightarrow10\\
\{b\}\leftrightarrow01\\
\{a,b\}\leftrightarrow11\\
$$
There are obviously $2^{\#A}$ numbers.
A: Proof by induction on the number of elements $n$ in a set $A$.
Base Case: Let $n=1$. Then $A_1={a_1}\Rightarrow P(A_1)=\{\{\emptyset\},\{a_1\}\} \Rightarrow |P(A_1)|=2^1=2^n$.
Inductive Hypothesis: Let $n=k$ and assume $|P(A_k)|=2^k$.
Inductive Step: Let $n=k+1$. Then $A_{k+1}=\{a_1,\ldots,a_k,a_{k+1}\}$.  Consider the fact that the power set of $A_{k+1}$ consists of two pieces: the power set $A_k$ and the set consisting of the Cartesian product of $P(A_k)$ and $a_{k+1}$ (call this set $P(A'_k)=P(A_k)\times a_{k+1}$).  As we noted above in the inductive hypothesis, $|P(A_k)|=2^k$. Note that $P(A'_k)$ has exactly $2^k$ elements in it by the properties of the Cartesian product. Then,
\begin{eqnarray*}
A_{k+1} &=& A_k \cup A'_k \\
\Rightarrow P(A_k+1) &=& P(A_k)+P(A'_k) \\
&=& 2^k+2^k \\
&=& 2\cdot2^k \\
&=& 2^{k+1}
\end{eqnarray*}
