Binomial Theorem Question..

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!

-

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}\;.$$

-

$$(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}$$

-

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}$.

-