5
$\begingroup$

Just studying for my combinatorics exam. My prof said there would be a question similar to this one on the exam, so I'm trying to sort this one out.

$\sum^{20}_{k=0} \binom{41}{k}$

I know if I can factor out $\dbinom{20}{k}$ then I can get the following:

$A\sum^{20}_{k=0}\binom{20}{k} * 1^k * 1^{n-k} = A(1+1)^{20}$

I just don't know how to get there...

Any help is greatly appreciated!

3 Answers 3

11

You’re on the wrong track, I’m afraid. The trick is to realize that your sum is exactly half of the full sum $\sum_{k=0}^{41}\binom{41}k$ because of the symmetry of the binomial coeffients: $\binom{41}{41-k}=\binom{41}k$.

$\begin{align*} 2^{41}&=\sum_{k=0}^{41}\binom{41}k\\ &=\sum_{k=0}^{20}\binom{41}k+\sum_{k=21}^{41}\binom{41}k\\ &=\sum_{k=0}^{20}\binom{41}k+\sum_{k=21}^{41}\binom{41}{41-k}\\ &=\sum_{k=0}^{20}\binom{41}k+\sum_{i=0}^{20}\binom{41}i&&\text{set }i=41-k\\ &=2\sum_{k=0}^{20}\binom{41}k\;, \end{align*}$

so that $\sum_{k=0}^{20}\binom{41}k=2^{40}\;.$

3

$(1+1)^{41}= \sum^{41}_{k=0} \binom{41}{k}$

but since the binomial coefficients are symmetrical around $\,k=21\,$ , we know that

$2^{41}= \sum^{20}_{k=0}\binom{41}{k}+\sum^{20}_{k=0}\binom{41}{k}\, $

thus

$2^{40}= \sum^{20}_{k=0} \binom{41}{k}$

2

Substitute $x=1$ in the expansion $(1+x)^{41}=\sum_0^{41}\binom{41}{k}x^k$ to obtain $\sum_0^{41}\binom{41}{k}=2^{41}$. Since $\binom{41}{k}=\binom{41}{41-k}$, we get $\sum_0^{20}\binom{41}{k}=\frac{1}{2}\sum_0^{41}\binom{41}{k}=2^{40}$.