How do I get a closed form expression for $\sum_{i=c}^{n} i\binom{i}{c}$? Note that the index ranges over the upper values of the binomial, not the lower.
I know computer algebra systems can give me an answer and I can then verify it using induction, but that's not what I want: I want to derive the closed form expression without using knowledge about what the answer looks like.
Best Answer
Note that the summation can be taken to start at $i=0$ with no change, as all added terms are$~0$.
After some playing around with this summation, I found the following approach the most useful. Without the factor $i$, one knows how to do partial sums of columns in Pascal's triangle $$ \sum_{i=0}^n\binom ic=\binom{n+1}{c+1}, $$ and more generally, taking differences, $$ \sum_{i=k+1}^n\binom ic=\binom{n+1}{c+1}-\binom{k+1}{c+1}. $$ Now realising that $i=\#\{\,k\in\Bbb N\mid k<i\,\}$, we can reorganise our summation $$ \begin{align} \sum_{i=0}^ni\binom ic & =\sum_{i=0}^n\sum_{k<i}\binom ic =\sum_{k=0}^{n-1}\sum_{i=k+1}^n\binom ic \\& =\sum_{k=0}^{n-1}(\binom{n+1}{c+1}-\binom{k+1}{c+1}) \\& =n\binom{n+1}{c+1}-\sum_{k=0}^{n-1}\binom{k+1}{c+1} \\& =n\binom{n+1}{c+1}-\binom{n+1}{c+2}. \end{align} $$
Added. Thinking about it I realise there is better than this ad hoc approach. The main difficulty with the question as formulated is that the factor $i$ increases in the wrong direction so that it is not a convolution. The recipe that will treat any summing any polynomial of the upper index times a column of Pascal's triangle is
In the example at hand, step 1. gives $\sum_{i=0}^n(n-i)\binom{n-i}c$, step 2. gives $n-i=n\binom i0-\binom i1$, and step 3. gives $$ \begin{align} \sum_{i=0}^n(n-i)\binom{n-i}c& =n\sum_{i=0}^n\binom i0\binom{n-i}c-\sum_{i=0}^n\binom i1\binom{n-i}c \\& =n\binom{n+1}{c+1}-\binom{n+1}{c+2}. \end{align} $$