choose!!

Algebra Level 3

find the value of the following sum $\sum_{n=0}^{100} \binom{100}{n}$ can be written as $\quad a^b\quad$ , where $a$ and $b$ are positive integers and $a$ is as small as possible. What is $a + b$ ?

The answer is 102.

2 solutions

Jake Lai
Jan 6, 2015

By the binomial theorem, $\displaystyle (x+y)^{n} \sum_{k=0}^{n} {n \choose k}x^{k}y^{n-k}$ . Setting $n = 100$ and $x = y = 1$ , we get

$\displaystyle (1+1)^{100} \sum_{k=0}^{100} {100 \choose k}$

Hence, $a^{b} = \boxed{2^{100}}$ .

(Note that $2^{100} = 4^{50} = 16^{25}$ which satisfy the condition $a < b$ .)

Massively overrated question, I suggest changing it to a level 2 or 3.

Jake Lai - 6 years, 5 months ago

i know, i had a simple miss-click it was meant for level 3. how do i change the level??

Aareyan Manzoor - 6 years, 5 months ago

Just edit the problem and wait for Calvin to change the question. The rating system will readjust it.

Jake Lai - 6 years, 5 months ago

Joel Tan
Jan 9, 2015

Other than binomial theorem or using the Pascal's identity, there is another common combinatorial proof:

Consider an n-element set S. The number of distinct subsets (including the empty set) is the sum of the number of 0-element, 1-element... n-element sets. This gives a total of X subsets where X is the answer to the question.

However, another way to count the number of subsets is to choose whether each element is included or not. There are 2 choices for each of n elements, a total of $2^{n}$ . When $n=100$ the answer is $2^{100}$ .

This gives a problem because there are multiple answers: $4^{50}, 16^{25}$ are also possible. So the answers are $102, 54, 41$ .

choose!!

The answer is 102.

2 solutions

0 pending reports