Sum of different combinations.

Question

I was trying to find the simplified form of ${100 \choose 0} + {100 \choose 1} + \ldots + {100 \choose 99} + {100 \choose 100}$. I was having a hard time finding a simple way to express the solution and I did not know how to do so without writing out the complete number. Does know what form I have to use?

Answer 1

The prior commenters have the correct answer of $2^{100}$. Here are some of my favorite proofs of this fact:

Firstly, using the Binomial theorem, $$2^{100} = (1 + 1)^{100} = \sum_{i=0}^{100}{100\choose i}1^i1^{100-i} = \sum_{i=0}^{100}{100\choose i}$$

A combinatorial proof of this fact is counting the number of ways we can paint $100$ objects either black or white. One way to count this is to make a binary choice for each ball to paint it black or to paint it white, so this number is $2^{100}$. The other way is to choose $i$ elements to be painted white, and let $i$ range over all possible values. This gives the value as $\sum_{i=0}^{100}{100\choose i}$. Thus, these two quantities are equal to each other.