# Evaluation $\sum\limits_{k=0}^n \binom{n}{k}$

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

Thank you.

-
Hint. $(1+1)^n = ???$ –  Arturo Magidin Apr 27 '12 at 17:19
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? –  Arturo Magidin Apr 27 '12 at 17:22
Its the expansion of the series $(1+x)^n$, put x=1, to get the sum –  Tomarinator Apr 27 '12 at 17:25
I'm quite sure this is a dupe... –  Ｊ. Ｍ. Apr 27 '12 at 17:37
J.M maybe this math.stackexchange.com/questions/18690/… –  Belgi Apr 27 '12 at 17:39

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.

-
Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle. –  Bill Dubuque Apr 27 '12 at 18:55
English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8. –  Cameron Buie Apr 27 '12 at 19:15
@CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent. –  André Nicolas Apr 27 '12 at 19:27