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.

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. 
