combinatorics - Binom - Combinatorical/Algebraic Proof

I've been given a couple of questions for an upcoming exams. We're having trouble answering these types of questions.

a. Calculate the value $\sum_{k=50}^{100} {100 \choose k}{k \choose 50}$ explicitly (without using the summation sign).

b. Calculate the value $\sum_{k=0}^{100} {100 \choose k}{200 \choose 200-k}$ explicitly (without using the summation sign).

c. Calculate the value $\sum_{k=2}^{50} k(k-1){50\choose k}$ explicitly (without using the summation sign).

d. Calculate the value $\sum_{k=0}^{20}{50\choose k}{50\choose 20- k}$ explicitly (without using the summation sign).

How do I solve these?

Thanks

Answer

We will give combinatorial arguments to evaluate these sums. Note that the numbers are specific to your sums but identical arguments can be used to prove the general cases.

A) Suppose there is a room of $100$ people and we want to select a cohort of at least $50$ them, say $k$. Moreover, we want to select $50$ of these $k$ people to get a special prize. The sum represents all ways to select a cohort of $50$ to $100$ people where $50$ get a special prize.

How else can we think of this? Instead, first pick the $50$ people to get a special prize. There are $\binom{100}{50}$ ways to do this. Then of the remaining $50$ people, select anywhere between $0$ and $50$ of them to also be in the cohort, which can be done in $2^{50}$ ways. Hence

$$
\sum_{k=50}^{100} \binom{100}{k} \binom{k}{50} = 2^{50} \binom{100}{50}.
$$

B) Consider a room of $300$ people, $100$ of which are male and $200$ are female. Suppose we want to select a committee of $200$ people. We can select $k$ males and $200-k$ females, of which there are $\binom{100}{k} \binom{200}{200-k}$ ways to do so. Summing from $k=0$ to $100$ gives all of the possible committees. Thus

$$
\sum_{k=0}^{100} \binom{100}{k} \binom{200}{200-k} = \binom{300}{200}.

$$

C) Suppose there are $50$ people and we must select a team of $k$ of them (between $2$ and $50$) where we designate a president and a vice president. There are $\binom{50}{k}$ ways to select the team, and $k(k-1)$ ways to select the president and vice president. Your sum is all ways to select such a team.

Equivalently, suppose first we chose a president and a vice president from the group of $50$. There are $50 \cdot 49$ ways to do so. Then we pick from $0$ to $48$ of the remaining people to be on the team. This can be done in $2^{48}$ ways. Hence

$$
\sum_{k=2}^{50} k(k-1)\binom{50}{k} = 50 \cdot 49 \cdot 2^{48}.
$$

D) This is identical to B) but with different numbers. The answer is

$$
\sum_{k=0}^{20} \binom{50}{k} \binom{50}{20-k} = \binom{100}{20}.
$$