Summing n times binomial(n,k) I'm trying to do $\sum_{n=a}^b \left( \begin{array}{rl} n \\ a \end{array} \right) n $ . 
Is there a formula, that anybody knows?
 A: We have, just by counting how many times each binomial term appears, that
$$
\sum_{n=a}^b  n \binom{n}{a}= b\sum_{n = a}^b\binom{n}{a} -\left( \sum_{n = a}^{b-1}\binom{n}{a}+\sum_{n = a}^{b-2} \binom{n}{a} + \cdots + \sum_{n = a}^a\binom{n}{a}\right)
$$
For instance, the term $\binom{b}{a}$ appears $b$ times in the original sum, and it appears $b$ times on the right-hand side as well. The term $\binom{a}{a}$ appears $a$ times in the original sum, and on the right-hand side it appears $b$ times, and is then subtracted $b-a$ times, which makes it a total of $a$ times.
Then, using the identity $\sum_{i = k}^l\binom{i}{k} = \binom{l+1}{k+1}$ multiple times, this gives us
$$
b\sum_{n = a}^b\binom{n}{a} -\left( \sum_{n = a}^{b-1}\binom{n}{a}+\sum_{n = a}^{b-2} \binom{n}{a} + \cdots + \sum_{n = a}^a\binom{n}{a}\right)\\
= b\binom{b+1}{a+1} - \left(\binom{b}{a+1} + \binom{b-1}{a+1}+\cdots + \binom{a+1}{a+1}\right)\\
= b\binom{b+1}{a+1} - \sum_{i = a+1}^b\binom{i}{a+1}\\
= b\binom{b+1}{a+1} - \binom{b+1}{a+2}
$$
A: If we allow to use the formula mentioned by Arthur
$$\sum_{i=k}^l \binom{i}{k}=\binom{l+1}{k+1}$$ then we can do it even shorter.
Note that
$$\sum_{n=a}^b n\binom{n}{a}=\sum_{n=a}^b (n+1)\binom{n}{a}-\sum_{n=a}^b \binom{n}{a}\\
=(a+1)\sum_{n=a}^b \binom{n+1}{a+1}-\sum_{n=a}^b \binom{n}{a}\\
=(a+1)\binom{b+2}{a+2}-\binom{b+1}{a+1}$$
A: Here’s a combinatorial derivation of a different formula.
I have $n+1$ white balls numbered from $0$ through $n$. I’m going to choose $m$ of these balls and paint them red. Then I’m going to choose one ball numbered below the highest-numbered red ball and put a gold star on it. I want to know the number of possible different outcomes.
Suppose that the highest-numbered red ball is ball number $k$; there are $k$ balls with lower numbers, so there are $\binom{k}m$ possible choices for the other $m$ red balls, and there are $k$ possible choices for the ball that gets the gold star. Summing over the possible values of $k$, we see that there are altogether
$$\sum_{k=m}^nk\binom{k}m$$
possible outcomes.
Alternatively, we can count the outcomes in two steps. We first count the outcomes that have a gold star on a red ball. That cannot be the highest-numbered red ball, so there are $\binom{n+1}{m+1}$ ways to choose the red balls and $m$ ways to choose one to be starred, for a total of $m\binom{n+1}{m+1}$ outcomes.
We then count the outcomes in which a white ball is starred. These outcomes have $m+2$ ‘special’ balls – i.e., balls that are either red or starred. There are $\binom{n+1}{m+2}$ ways to choose these balls. The starred ball can then be any of them except the one with the highest number, the remaining $m+1$ balls being red, so there are $(m+1)\binom{n+1}{m+2}$ outcomes of this type. Altogether, then, we have
$$\sum_{k=m}^nk\binom{k}m=m\binom{n+1}{m+1}+(m+1)\binom{n+1}{m+2}\;.$$
This can be rewritten in a variety of ways, e.g.,
$$\begin{align*}
m\binom{n+1}{m+1}+(m+1)\binom{n+1}{m+2}&=m\left(\binom{n+1}{m+1}+\binom{n+1}{m+2}\right)+\binom{n+1}{m+2}\\
&=m\binom{n+2}{m+2}+\binom{n+1}{m+2}
\end{align*}$$
and
$$\begin{align*}
m\binom{n+1}{m+1}+(m+1)\binom{n+1}{m+2}&=(m+1)\left(\binom{n+1}{m+1}+\binom{n+1}{m+2}\right)-\binom{n+1}{m+1}\\
&=(m+1)\binom{n+2}{m+2}-\binom{n+1}{m+1}\;,
\end{align*}$$
the latter being Tintarn’s result.
A: Use generating functions. First:
$\begin{align}
\sum_{n \ge 0} \binom{n}{a} z^n
  &= \frac{z^a}{(1 - z)^{a + 1}} \\
z \frac{\mathrm{d}}{\mathrm{d} z} \sum_{n \ge 0} \binom{n}{a} z^n
  &= \sum_{n \ge 0} n \binom{n}{a} z^n \\
  &= \frac{z^a (z + a)}{(1 - z)^{a + 2}}
\end{align}$
But also, to get partial sums you divide by $1 - z$:
$$
\sum_{k \ge 0} \left( \sum_{0 \le n \le k} n \binom{n}{k}\right) z^k
  = \frac{z^a (z + a)}{(1 - z)^{a + 3}}
$$
Now you are interested in the coefficient of $z^b$:
$\begin{align}
\sum_{0 \le n \le b} n \binom{n}{a}
  &= [z^b] \frac{z^a (z + a)}{(1 - z)^{a + 3}} \\
  &= [z^b] (z^{a + 1} + a z^a) \sum_{k \ge 0} (-1)^k \binom{-a - 3}{k} z^k \\
  &= [z^b] (z^{a + 1} + a z^a)
             \sum_{k \ge 0} \binom{a + 3 + k - 1}{a + 3 - 1} z^k \\
  &= [z^{b - a - 1}] \sum_{k \ge 0} \binom{a + 3 + k - 1}{a + 3 - 1} z^k
       + a [z^{b - a}]\sum_{k \ge 0} \binom{a + 3 + k - 1}{a + 3 - 1} z^k \\
  &= \binom{a + 2 + b - a - 1}{a + 2} + a \binom{a + 2 + b - a}{a + 2} \\
  &= \binom{b + 1}{a + 2} + a \binom{b + 2}{a + 2}
\end{align}$
