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


marked as duplicate by J. M. is a poor mathematician, Mike Spivey, Asaf Karagila, anon, t.b. Sep 30 '11 at 10:20

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.

  • 3
    $\begingroup$ Hint: what is $(1+1)^k$ ? $\endgroup$ – Sebastian Sep 27 '11 at 9:55
  • $\begingroup$ See this question and its answer. There the recommended substitution is $x=2$ that doesn't quite work here. But I really think that you should be able to find a substitution that works :-). But I'm also afraid that this question may get closed as essentially a duplicate... I mean, are you seriously saying that they haven't taught you this much at... wherever you study. $\endgroup$ – Jyrki Lahtonen Sep 27 '11 at 9:57
  • $\begingroup$ @Sebastian: Indeed, Gortaur said the same thing, much simpler than I thought. $\endgroup$ – Freeman Sep 27 '11 at 9:59
  • $\begingroup$ @JyrkiLahtonen: Well I have never come across that, and due to how the question approached the use of this identity it was unclear as to why, just being a bit slow. $\endgroup$ – Freeman Sep 27 '11 at 10:02
  • 1
    $\begingroup$ @JyrkiLahtonen: Thanks, I study at Oxford, and frankly it's embarrassing I didn't know that, but I asked a fellow student and he went through the same process of trying to prove it and failing by over complicating it. So I don't feel too bad.. $\endgroup$ – Freeman Sep 27 '11 at 10:24

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

  • $\begingroup$ That's excellent! and much simpler than I was expecting, thanks! $\endgroup$ – Freeman Sep 27 '11 at 9:58

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

  • $\begingroup$ Thanks, although I may have made myself look like I knew a lot less than I do by asking this question, turns out it was just a gap in my knowledge, due to how fast we cover material. $\endgroup$ – Freeman Sep 27 '11 at 10:20

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