Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thank you.

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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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