Why does $\sum\limits_{i=0}^k {k\choose i}=2^k$ 
Possible Duplicate:
Proving a special case of the binomial theorem 

Can anyone explain to me why
$$\sum\limits_{i=0}^k {k\choose i}=2^k\,?$$
Thanks in advance
 A: I think the usual way to explain it is to use Newton Binomial formula, i.e.
$$
(a+b)^k = \sum\limits_{i=0}^k {k\choose i}a^ib^{k-i}
$$
then put $a=b=1$, so you have $2^k$ on the left-hand side and the sum you're interested in on the right-hand side.
The Binomial formula you can prove easily by induction - but I think that for your example if you don't know the Binomial formula, it's even should be easier to prove by induction that
$$
\sum\limits_{i=0}^k {k\choose i} = 2^k.
$$
A: Obligatory combinatorial interpretation: the number of ways of picking a subset from $\{1,2,,\dots,k\}$ is equal to the number of ways of making a choice of whether or not $i$ is in the subset for $i=1,2,\dots,k$ independently, which is $2^k$ (kind of like having $k$ numbered on/off switches all in a row, where "on" means the switch's number gets put into the subset). Alternatively, it's the number of ways of picking $0$ elements out, plus the number of ways of picking $1$ elements out, plus the number of ways of picking $2$ elements out, $\dots$ plus the number of ways of picking all $k$ elements out, which is $\sum_{i=0}^k{k\choose i}$.
