3
$\begingroup$

Please help me to evaluate combinatorially the following sum: $$\sum_{k=0}^n \binom{n}{k}$$

Thank you.

  • 0
    **Hint.** $(1+1)^n = ???$2012-04-27
  • 3
    **Alternative Hint.** If you choose either $0$, or $1$, or $2$, or $3$, or $4,\ldots,$ or $n$ elements out of $n$, then you are just choosing "some" objects out of $n$ possibilities. How many ways are there of doing that?2012-04-27
  • 2
    Its the expansion of the series $(1+x)^n$, put x=1, to get the sum2012-04-27
  • 1
    I'm quite sure this is a dupe...2012-04-27
  • 1
    J.M maybe this http://math.stackexchange.com/questions/18690/algebraic-proof-that-sum-limits-i-0n-binomni-2n2012-04-27

2 Answers 2

11

We use the powerful strategy of counting the same thing in two different ways. We have a set $S$ of $n$ spices. We ask how many different subsets this set has.

Line up the spices in order on a shelf. Go gradually down the shelf, saying yes or no to each spice in turn. At each spice, we have two choices. So there is a total of $2^n$ choices, and hence $S$ has $2^n$ subsets.

For any $k$, there are by definition $\binom{n}{k}$ ways to choose $k$ spices from the set $S$. So $S$ has $\binom{n}{k}$ subsets with $k$ elements. Summing over all $k$ from $0$ to $n$ gives us a different way of counting all the subsets.

Both counting methods are correct, so they must give the same answer. It follows that $$\sum_{k=1}^n \binom{n}{k}=2^n.$$

Remark: Bhaskara once asked the following question. There are $6$ basic flavours (sour, sweet, bitter, and so on). How many different-flavoured dishes can one make by using flavours selected from these? He gave the answer $63$, leaving out the empty set of flavours. He did not know about English cooking.

  • 0
    Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle.2012-04-27
  • 2
    English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8.2012-04-27
  • 0
    @CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.2012-04-27