Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by Lord_Farin, egreg, user1337, Daniel Fischer, azimut Nov 28 '13 at 15:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

add comment

5 Answers 5

up vote 7 down vote accepted

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!

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
This answers the question in the subject heading, but doesn't explicitly deal with the one in the body of the question. –  Michael Hardy Aug 24 '11 at 22:25
add comment

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.

share|improve this answer
    
The obvious bijection between the subsets of $X$ and binary numbers between $0$ and $2^{N}-1$ implcitly suggested by this answer seems very natural to me, but maybe a little more explanation might be given. –  Geoff Robinson Dec 22 '11 at 17:17
add comment

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.