Algebraic proof that collection of all subsets of a set (power set) of $N$ elements has $2^N$ elements

Question

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.

Answer 1

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!

Answer 2

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.

Answer 3

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}$.

Answer 4

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.

Answer 5

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.