Closed form expression for unusual sum of binomial coefficients

Question

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.

Answer 1

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

1. Write the polynomial factor in terms for the distance to the final index, so as to get a convolution $\sum_iP(i)\binom{n-i}c$;
2. Express the polynomial $P(i)$ as combination of binomial coefficients $\binom ik$;
3. For each term, apply the upper-index variation of the Vandermonde convolution: $$ \sum_{i=0}^n\binom ik\binom{n-i}c=\binom{n+1}{k+c+1}. $$

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

Answer 2

Just to answer to the question in some comments: If I read things correctly, then this asks for a matrixmultiplication like this,

$$\small \begin{matrix} . & . & . & . & . & . & | & 1 & . & . & . & . & . & | \\ . & . & . & . & . & . & | & 1 & 1 & . & . & . & . & | \\ . & . & . & . & . & . & | & 1 & 2 & 1 & . & . & . & | \\ . & . & . & . & . & . & | & 1 & 3 & 3 & 1 & . & . & | \\ . & . & . & . & . & . & | & 1 & 4 & 6 & 4 & 1 & . & | \\ . & . & . & . & . & . & | & 1 & 5 & 10 & 10 & 5 & 1 & | \\ - & - & - & - & - & - & + & - & - & - & - & - & - & + \\ . & 1 & 2 & 3 & 4 & 5 & | & y_0 & y_1 & y_2 & y_3 & y_4 & y_5 & | \\ - & - & - & - & - & - & + & - & - & - & - & - & - & + \end{matrix} $$ where the number of columns of the left vector (and the number of rows of the matrix) is given in the value of the indeterminate $n$... (If the OP wants, he can insert that scheme in his question...)

ALso, there was an answer given which points to the derivatives of some function, which I think is a good hint: the left vector could be written as $[0,1x,2x^2,3x^3,...,nx^n]$ and then one could observe the occuring expressions for the sum (getting $y_0$ using column 0 of the matrix), find a general expression for them and their derivatives (getting $y_k \cdot k!$ using the other columns of the matrix), and then one would insert $1$ for $x$...(but I think it's even easier when detecting the type of sum which is involved here because it is a very usual one...)

---

A further hint: note that the dotproduct $y_0$ seen as function of $x$, where $x$ is inserted in the left vector as indicated above, gives the expression: $$ y_0(x,n) =x {1-x^n\over (1-x)^2} - nx \cdot{ x^n \over (1-x)} $$ (which has be derived from the expression for the finite geometric sum and their derivative).
To evaluate it (and the derivatives $$ y_1(x,n)=y_0(x,n)'/1! \\ y_2(x,n)=y_0(x,n)''/2! \\ ...$$) at $x=1$ one has to cancel the $(1-x)$-factor and then, I think, one has to use L'Hospital's rule - but I didn't proceed to this for the moment)