4
$\begingroup$

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

Thank you.

  • 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

14

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
    @CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.2012-04-27