Algebraic proof that collection of all subsets of a set (power set) of $N$ elements has $2^N$ elements In other words, is there an algebraic proof showing that $\sum_{k=0}^{N} {N\choose k} = 2^N$? I've been trying to do it some some time now, but I can't seem to figure it out.
 A: An algebraic proof:
Expand $(1+x)^n$ using  binomial theorem which gives $$(1+x)^n={n\choose 0}x^0 + {n\choose 1}x^1 + {n\choose 2}x^2 + {n\choose 3}x^3 + \cdots + {n\choose n}x^n$$
set $x = 1$ hence,
$$(1+1)^n={n\choose 0}1^0 + {n\choose 1}1^1 + {n\choose 2}1^2 + {n\choose 3}1^3 + \cdots + {n\choose n}1^n$$
$$\Rightarrow 2^n={n\choose 0} + {n\choose 1} + {n\choose 2} + {n\choose 3} + \cdots + {n\choose n}$$
$$\Rightarrow 2^n=\sum_{k=0}^{n} {n\choose k}$$
QED!
A: By the binomial theorem, $\sum_{k=0}^{N} {N\choose k} = (1+1)^N = 2^N$.
However, note that the binomial theorem admits a natural combinatorial proof, which exactly relates coefficients with subsets. So the argument above is not exclusively algebraic in nature.
A: I don't know what you mean by "algebraic".  Notice that if $N$ is $0$, we have the empty set, which has exactly one subset, namely itself.  That's a basis for a proof by mathematical induction.
For the inductive step, suppose a set with $N$ elements has $2^N$ subsets, and consider a set of $N+1$ elements that results from adding one additional element called $x$ to the set.  All of the $2^N$ subsets of our original set of $2^N$ elements are also subsets of our newly enlarged set that contains $x$.  In addition, for each such set $S$, the set $S\cup\{x\}$ is a subset of our enlarged set.  So we have our original $2^N$ subsets plus $2^N$ new subsets---the ones that contain $\{x\}$.  The number of subsets of the enlarged set is thus $2^N + 2^N$.
Now for an "algebraic" part of the arugment: $2^N + 2^N = 2^{N+1}$.
A: Another approach is identifying the powerset $\mathcal P \, X$ of a set $X$ with the set of functions $X \to 2$ (that is to say with the set of idicator functions of the subsets). Of course this is only useful if you have any previous results on cardinalities of sets of functions between (finite) sets.
A: Another inductive proof that is somewhat more algebraic (in the sense of not using the combinatorial interpretation of $\binom{n}{k}$): check the base cases, and note that
$$
\sum_{k=0}^{n-1} \binom{n}{k} + \sum_{k=0}^{n-1} \binom{n}{k+1} = \sum_{k=0}^{n-1} \binom{n+1}{k+1}
$$
Of course, the combinatorial proofs are much more enlightening. 
