5
$\begingroup$

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.

$\endgroup$
0

5 Answers 5

8
$\begingroup$

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!

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This answers the question in the subject heading, but doesn't explicitly deal with the one in the body of the question. $\endgroup$ Aug 24, 2011 at 22:25
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Dec 22, 2011 at 17:17
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .