$\sum_{k=1}^{n} {k\choose m} {k}$
I have tried to expand it, but the m is pretty annoying.
Any ideas to get rid of the summation and give a simple formula?
There is a part before $\sum_{k=1}^{n} {k\choose m} {\frac{1}{k}}$, see if it gives any ideas.
Best Answer
To handle this, you can first absorb the factor $k$ into the binomial coefficient. Actually a factor $k+1$ absorbs better: $(k+1)\binom km=(m+1)\binom{k+1}{m+1}$. So you can write $$ \sum_{k=0}^nk\binom km = \sum_{k=0}^n(m+1)\binom{k+1}{m+1}-\sum_{k=0}^n\binom km $$ then using the identity $\sum_{k=0}^n\binom km=\binom {n+1}{m+1}$, this simplifies to $$ \sum_{k=0}^nk\binom km =(m+1)\binom{n+2}{m+2}-\binom{n+1}{m+1} =\frac{mn+m+n}{m+2}\binom{n+1}{m+1}. $$
Here's are combinatorial arguments for the the equalities used. For the absortion law, $(k+1)\binom km$ counts the number of ways to select among $k+1$ candidates a president and $m$ vice-presidents, which can also be done by selecting the $m+1$ (vice)presidents and then choosing a president among them.
For the identity $\sum_{k=0}^n\binom km=\binom {n+1}{m+1}$, if one must choose $m+1$ out of the $n+1$ numbers $0,1,2,\ldots,n$, one can start choosing an element $k$ that is going to be the largest element of the selection; then to choose the remaining elements you can choose any subset of $m$ of the $k$ numbers that are less than$~k$. All in all you got $\sum_{k=0}^n\binom km$ choices, which well get every outcome exactly once.
Added. The identity $\sum_{k=0}^n(k+1)\binom km =(m+1)\binom{n+2}{m+2}$ can be given the following direct, if somewhat convoluted, combinatorial interpretation. The RHS counts the number of ways to choose a subset $S$ of $n+2$ numbers out of $\{0,\ldots,n+1\}$, and mark a non-maximal chosen number. Such a choice can also be obtained by first choosing $k+1=\max(S)$ (determining $0\leq k\leq n$) and then the marked element among $\{0,1,\ldots,k\}$ (for a factor $k+1$), and finally the $m$ remaining (non maximal, unmarked) elements if $S$, in one of $\binom km$ possible ways; the LHS counts these choices. Note that no such procedure involving $\max(S)$ would exist if we had allowed $\max(S)$ itself to be marked.