What is this binomial sum? I'm trying to figure out what this sum is equal to:
$$\sum^n_{k=0}k \binom{m-k}{m-n}$$
I thought there are n turns and on each turn you pick 1 object from k objects ($\binom{k}{1}=k$) and also pick $m-n$ objects from $m-k$ objects. So I thought we pick a total of $m-n+1$ objects from $m-k+k=m$ objects, giving 
$$\sum^n_{k=0}k \binom{m-k}{m-n}=\binom{m}{m-n+1}$$
But I plugged in some test numbers and this didn't seem to work. What am I thinking wrong?
 A: Let’s look at it a little differently. Suppose that you want to choose a set of $m-n+2$ numbers from the set $A=\{0,1,\ldots,m\}$. If $S$ is such a set, let $k_S$ be the second-smallest member of $S$. Then $S$ has $1$ member smaller than $k_S$ and $m-n$ members larger than $k_S$. For a given $k$ there are $k$ ways to pick one smaller member of the set $A$ and $\binom{m-k}{m-n}$ ways to pick $m-n$ larger members of $A$, so there are 
$$k\binom{m-k}{m-n}$$
ways to choose $S$ with $k_S=k$. Summing over the possible values of $k$ gives the total number of such subsets, which is of course
$$\binom{|A|}{m-n+2}=\binom{m+1}{m-n+2}\;.$$
The problem with your approach is that when you choose one of the first $k$ and $m-n$ of the last $n-k$ elements of $[m]$, you’re not just making a selection of $m-n+1$ elements of $[m]$: you’re also specifying a break-point between the first one and the last $m-n$.
A: I tried the following calculations :
$$
\eqalign{
\sum_{k=0}^n k \binom{m-k}{m-n} &= \sum_{k=0}^n (m+1-(m+1-k)) \binom{m-k}{m-n} \cr
&= \sum_{k=0}^n (m+1)\binom{m-k}{m-n} - \sum_{k=0}^n (m+1-k) \binom{m-k}{m-n} \cr
&= \sum_{k=0}^n (m+1)\binom{m-k}{m-n} - \sum_{k=0}^n (m-n+1) \binom{m-k+1}{m-n+1} \cr
&= (m+1)\sum_{k=0}^n \binom{m-k}{m-n} - (m-n+1) \sum_{k=0}^n  \binom{m-k+1}{m-n+1} \cr
}
$$
Let
$$
A=\sum_{k=0}^n \binom{m-k}{m-n}\ \ \ and\ \ \ B=\sum_{k=0}^n \binom{m-k+1}{m-n+1} 
$$
We evaluate first $A$,
$$
\eqalign{
A &= \sum_{0 \le k \le n} \binom{m-k}{m-n} \cr
  &= \sum_{0 \le m-k \le n} \binom{m-(m-k)}{m-n} \cr
  &= \sum_{-m \le -k \le -(m-n)} \binom{k}{m-n} \cr
  &= \sum_{0 \le k \le m} \binom{k}{m-n} \cr
  &= \binom{m+1}{m-n+1} \cr
}
$$
Similar calculations for $B$ give
$$
\eqalign {
  B &= \binom{m+2}{m-n+2} \cr
}
$$
To conclude finally that
$$
\sum_{k=0}^n k \binom{m-k}{m-n} = (m+1)\binom{m+1}{m-n+1} - (m-n+1)\binom{m+2}{m-n+2}
$$
A: Starting from
$$\sum_{k=0}^n k {m-k\choose m-n}
= \sum_{k=0}^n k {m-k\choose n-k}
\\= \sum_{k=0}^n k [z^{n-k}] (1+z)^{m-k}
= [z^n] (1+z)^m \sum_{k=0}^n k z^k (1+z)^{-k}$$
we see that there is no contribution to the coefficient extractor when
$k\gt n$ so we may extend $k$ to infinity:
$$[z^n] (1+z)^m \sum_{k\ge 0} k z^k (1+z)^{-k}
= [z^n] (1+z)^m \frac{z/(1+z)}{(1-z/(1+z))^2}
\\ = [z^n] (1+z)^m z (1+z) =
[z^{n-1}] (1+z)^{m+1} = {m+1\choose n-1}.$$
