How to prove: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$ Show that if $m$ and $n$ are integers with $0\leq m<n$ then $$\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$$
Attempts:


*

*$(-1)^{k}\binom{n}{k}$ is the coefficient of $x^{k}$ in the expansion of $(1-x)^{n}$

*And $\binom{k-1}{m}$ is the coefficient of $x^{m}$ in the expansion of $(1+x)^{k-1}$. 
Thats all what I could come up with.
 A: Following the hint of Arthur, note that $$\frac{1}{m!}\sum_{k=1}^{n}\dbinom{n}{k}\left(-1\right)^{k}x^{k-1}=\frac{\left(1-x\right)^{n}-1}{xm!}
 $$ and if we differentiate the LHS $m$ times, we get $$\frac{1}{m!}\sum_{k=1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\left(k-1\right)\left(k-2\right)\cdots\left(k-m\right)x^{k-m-1}=\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\frac{\left(k-1\right)!}{m!\left(k-m-1\right)!}x^{k-m-1}
 $$ so we have $$\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\dbinom{k-1}{m}=\frac{1}{m!}\frac{d^{m}}{dx^{m}}\left(\frac{\left(1-x\right)^{n}-1}{x}\right)_{x=1}
 $$ now note that $$\frac{d}{dx}\left(\frac{\left(1-x\right)^{n}}{x}-\frac{1}{x}\right)=-\frac{n\left(1-x\right)^{n-1}}{x}-\frac{\left(1-x\right)^{n}}{x^{2}}+\frac{1}{x^{2}}
 $$ and $$\frac{d}{dx}\left(-\frac{n\left(1-x\right)^{n-1}}{x}-\frac{\left(1-x\right)^{n}}{x^{2}}+\frac{1}{x^{2}}\right)=\frac{2\left(1-x\right)^{n}}{x^{3}}+\frac{2n\left(1-x\right)^{n-1}}{x^{2}}+\frac{n\left(n-1\right)\left(1-x\right)^{n-2}}{x}-\frac{2}{x^{3}}
 $$ and so on, so you can see that, since $m<n
 $ we have only one term that doesn't vanish at $x=1$. Hence $$\frac{1}{m!}\frac{d^{m}}{dx^{m}}\left(\frac{\left(1-x\right)^{n}-1}{x}\right)_{x=1}=\frac{1}{m!}\left(-1\right)^{m+1}m!=\left(-1\right)^{m+1}
 $$ so finally 

$$\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\dbinom{k-1}{m}=\color{red}{\left(-1\right)^{m+1}}$$ 

as wanted.
A: For  those who  enjoy integrals  here  is another  approach using  the
Egorychev method as presented in many posts by @FelixMarin and also by
@MarkusScheuer.
Suppose we seek to verify that
$$\sum_{k=m+1}^n (-1)^k {n\choose k} {k-1\choose m} = (-1)^{m+1}.$$
First proof. Introduce
$${k-1\choose m} = {k-1\choose k-1-m} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k-m}} (1+z)^{k-1} \; dz.$$
Now clearly when  $k\le m$ this vanishes so we may  lower the limit in
the sum to $k=0.$ We obtain
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{z^m}{1+z}
\sum_{k=0}^n {n\choose k} (-1)^k \frac{(1+z)^k}{z^k}  \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{z^m}{1+z}
\left(1-\frac{1+z}{z} \right)^n \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{z^m}{1+z}
\frac{(-1)^n}{z^n} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(-1)^n}{z^{n-m} (1+z)} \; dz
= (-1)^n (-1)^{n-m-1} = (-1)^{m+1}.$$
Second proof. Introduce
$${k-1\choose m} = {k-1\choose k-1-m} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m+1}} \frac{1}{(1-z)^{k-m}} \; dz.$$
Now for $1\le k\le m$ this is  $[z^m] (1-z)^{m-k} = 0$ so we may again
extend the summation back to $k=0$,  taking care of the value at $k=0$
which is $(-1)^m.$ We obtain
$$-(-1)^m + \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m+1}} (1-z)^m 
\sum_{k=0}^n {n\choose k} \frac{(-1)^k}{(1-z)^k}
\; dz
\\ = -(-1)^m + \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m+1}} (1-z)^m 
\left(1-\frac{1}{1-z}\right)^n
\; dz
\\ = -(-1)^m + \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{m-n+1}} \frac{(-1)^n}{(1-z)^{n-m}} \; dz.$$
Note  however that  we  have $m\lt  n$  so the  contribution from  the
integral vanishes, once more leaving just $$(-1)^{m+1}.$$
A: Here is a variation based upon OPs attempts. In order to do so it's convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g.
\begin{align*}
(-1)^k\binom{n}{k}=[x^k](1-x)^n
\end{align*}

We obtain for $0\leq m < n$
\begin{align*}
\sum_{k=m+1}^{n}&(-1)^{k}\binom{n}{k}\binom{k-1}{m}\\
&=\sum_{k=0}^{\infty}(-1)^{k}\binom{n}{k}\binom{k-1}{k-1-m}\tag{1}\\
&=\sum_{k=0}^\infty[x^k](1-x)^n [t^{k-1-m}](1+t)^{k-1}\tag{2}\\
&=[t^{-1-m}]\frac{1}{1+t}\sum_{k=0}^\infty(1+t)^kt^{-k}[x^{k}](1-x)^n \tag{3}\\
&=[t^{-1-m}]\frac{1}{1+t}\left(1-\frac{1+t}{t}\right)^n\tag{4}\\
&=[t^{-1-m}]\frac{1}{1+t}\left(-\frac{1}{t}\right)^n\\
&=(-1)^n[t^{n-m-1}]\sum_{j=0}^\infty(-t)^j\tag{5}\\
&=(-1)^{m+1}\tag{6}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we use  the binomial identity
$
\binom{p}{q}=\binom{p}{p-q}
$ and extend the limits  of  the  sum  without changing anything since we are adding zeros only. 

*In (2) we apply the coefficient of operator twice.

*In (3) we do some rearrangements by using the linearity of the coefficient of operator  and  we also  use  the  rule
\begin{align*}
[t^{p+q}]A(t)=[t^p]t^{-q}A(t)
\end{align*}

*In (4) we use the substitution rule
\begin{align*}
A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[x^k]A(x)\\
\end{align*}

*In (5) we write $t^{-n}$ as part of the coefficient of operator (rule from (3)) and use the geometric series expansion of $\frac{1}{1+t}$.

*In (6) we select the coefficient of $t^{n-m-1}$.
A: The result can also be proved fairly easily by induction on $n$. First note that there’s no need to specify the limits of summation: if $k>n$ or $k<m+1$, one of the binomial coefficients is $0$ anyway. Suppose that
$$\sum_k(-1)^k\binom{n}k\binom{k-1}m= (-1)^{m+1}$$
whenever $0\le m<n$. Then for $m<n$ we have
$$\begin{align*}
\sum_k(-1)^k\binom{n+1}k\binom{k-1}m&=\sum_k(-1)^k\left(\binom{n}k+\binom{n}{k-1}\right)\binom{k-1}m\\
&=\sum_k(-1)^k\binom{n}k\binom{k-1}m+\sum_k(-1)^k\binom{n}{k-1}\binom{k-1}m\\
&=(-1)^{m+1}+\sum_k(-1)^k\binom{n}{k-1}\binom{k-1}m\\
&=(-1)^{m+1}-\sum_k(-1)^k\binom{n}k\binom{k}m\\
&=(-1)^{m+1}-\sum_k(-1)^k\binom{n}m\binom{n-m}{n-k}\\
&=(-1)^{m+1}-\binom{n}m\sum_k(-1)^k\binom{n-m}k\\
&=(-1)^{m+1}\;,
\end{align*}$$
since $\sum_k(-1)^k\binom{r}k=0$ for $r\in\Bbb Z^+$.
The case $m=n$ is trivial, as the summation has only one non-zero term, the one for $k=n+1$:
$$(-1)^{n+1}\binom{n+1}{n+1}\binom{n}n=(-1)^{n+1}\;.$$
Added: In fact, that suggests a combinatorial proof of the original identity. Suppose that we have $n$ white balls numbered $1$ through $n$. For a given $k$ there are $\binom{n}k\binom{k-1}m$ ways to choose $k$ of these balls, paint them red, set aside the red ball with the largest number, and then choose $m$ of the remaining $k-1$ red balls to paint blue. In the end we have the following as possible outcomes: a set of $m$ blue balls; a set of $k-m$ red balls, one of which has a larger number than any of the blue balls; and $n-k$ white balls. Clearly the possible values of $k$ are the integers $m+1,\ldots,n$.
Alternatively, we can categorize these outcomes by the specific set of blue balls and the number of the largest-numbered red ball. For a fixed set $B$ of $m$ blue balls and largest-numbered red ball $\ell$, the numbers on the remaining red balls can be any subset $R$ of $[\ell-1]\setminus B$, and the total number of red and blue balls (corresponding to $k$ above) is $|R|+m+1$. These outcomes therefore contribute
$$\begin{align*}
\sum_{r=0}^{\ell-1-m}\binom{\ell-1-m}r(-1)^{r+m+1}&=(-1)^{m+1}\sum_r\binom{\ell-1-m}r(-1)^r\\
&=(-1)^{m+1}[\ell=m+1]\;,
\end{align*}$$
where $[\ell=m+1]$ is an Iverson bracket.
That is, only for $B=[m]$ and $\ell=m+1$ do these outcomes have a non-zero contribution, and in that case the contribution is $(-1)^{m+1}$.
