Discrete Math - Calculating $sum_{k}^{n}$

This will come too late to be of help before the exam, but the ideas may be useful to you at some later point.

Sometimes the easiest way to attack one of these questions is to find a useful combinatorial interpretation. For instance, imagine that you have $25$ white balls numbered $1$ through $25$. Then $binom{25}kbinom{k}2$ can be thought of as the number of ways to choose $k$ of them to paint red and then to choose $2$ of the red balls and attach a gold star to each of them. In the end we have $25-k$ white balls and $k$ red balls, two of which have gold stars.

$$sum_{k=2}^{25}binom{25}kbinom{k}2$$

is then the total number of possible outcomes when we allow all possible values of $k$.

We can generate the same outcomes by first choosing $2$ balls to be painted red and given gold stars, and then choosing any subset of the remaining $23$ balls to be painted red: choosing $ell$ balls in that last step gives the outcomes corresponding to $k=ell+2$. And if we think of it this way, it’s easy to get the final result in a closed form: there are $binom{25}2$ ways to choose the balls that get gold stars, and there are $2^{23}$ ways to choose a subset of the remaining $23$ balls to be painted red, so

$$sum_{k=2}^{25}binom{25}kbinom{k}2=2^{23}binom{25}2=frac{25cdot24}2cdot2^{23}=25cdot24cdot2^{22},.$$

For the second one I would first use a very basic identity to get rid of the annoying factor of $k$:

$$kbinom{10}k=10binom9{k-1},.$$

(Combinatorial interpretation: Picking a team of $k$ people from a pool of $10$ and then designating one of them captain produces the same outcomes as first picking one of the $10$ to be captain and then picking $k-1$ more people from the $9$ remaining to fill out the team of $k$.)

Thus,

$$begin{align*} sum_{k=1}^{10}kbinom{10}kbinom{20}{10-k}&=10sum_{k=1}^{10}binom9{k-1}binom{20}{10-k}\ &=sum_{k=0}^9binom9kbinom{20}{9-k},.tag{1} end{align*}$$

If you know the Vandermonde identity, you can simply apply it. If not, imagine that you have a pool of $9$ men and $20$ women, from which you want to select a committee of $9$ people. There are $binom9kbinom{20}{9-k}$ ways to choose a committee of $9$ people that contains exactly $k$ men, so $(1)$ is just the total number of possible committees of $9$ people, and that is clearly $binom{29}9$.