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?
Asked
Active
Viewed 75 times
-1
-
1It is equal to $2^{100}$. – Peter Foreman Jul 04 '19 at 17:03
-
2There are a lot of ways to see it's $2^{100}$. There's a combinatorial argument, a pictorial argument via Pascal's triangle, or an identity based argument. – Rushabh Mehta Jul 04 '19 at 17:04
1 Answers
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.
Sohom Paul
- 754