A binomial identity from Mathematical Reflections Here is the problem:
Let $m,n$ be positive integers with $n>m$. Prove that
$\displaystyle\sum_{k=0}^{\lfloor\frac{n+m}2\rfloor} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{n-1}=\binom{n}{m+1}$
This problem is O243 of Mathematical Reflections. A solution had been published using complex integration (https://www.awesomemath.org/assets/PDFs/MR5sol(1).pdf). However, I would like to see a solution using the difference operator, if any, since the form of the summand brings this to mind.
 A: First of all, it is worth stating explicitly that the problem assumes that $\binom{n}{k}$ is zero when $n < 0$ or $n>k$, even for $k\geqslant 0$. Indeed, otherwise
In[61]:= Table[
 Sum[(-1)^k Binomial[n, k] Binomial[n + m - 2 k, n - 1], {k, 0, 
   n}], {n, 1, 5}, {m, 0, n - 1}]

Out[61]= {{0}, {0, 0}, {0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0, 0}}

With those restrictions in place the claimed result is indeed reproduced:
In[65]:= Table[
 Sum[(-1)^k Binomial[n, k] Binomial[n + m - 2 k, n - 1] Boole[
    0 <= n - 1 <= n + m - 2 k], {k, 0, n}], {n, 1, 5}, {m, 0, n - 1}]

Out[65]= {{1}, {2, 1}, {3, 3, 1}, {4, 6, 4, 1}, {5, 10, 10, 5, 1}}

In[66]:= Table[Binomial[n, m + 1], {n, 1, 5}, {m, 0, n - 1}]

Out[66]= {{1}, {2, 1}, {3, 3, 1}, {4, 6, 4, 1}, {5, 10, 10, 5, 1}}

With this said, the upper bound of summation over $k$ is $m_\ast = \left\lfloor \frac{m+1}{2} \right\rfloor$:
$$
   \mathcal{S}(n,m)= \sum_{k=0}^{m_\ast} (-1)^k \binom{n}{k} \binom{n+m-2k}{n-1} 
$$
The summand is the hypergeometric term, meaning that 
$$
 r(k) = \frac{c_{k+1}}{c_k} = \frac{(-1)^{k+1} \binom{n}{k+1} \binom{n+m-2(k+1)}{n-1} }{(-1)^k \binom{n}{k} \binom{n+m-2k}{n-1} } = \frac{-n+k}{k+1} \frac{-\frac{m+1}{2} + k}{-\frac{m+n-1}{2} + k} \frac{-\frac{m}{2} + k}{-\frac{m+n}{2}+k}
$$
and therefore
$$
   c_k = c_0 \prod_{q=1}^{k} r(q) = \binom{m+n}{n-1} \frac{(-n)_k}{k!} \frac{\left(-\frac{m}{2}\right)_k \cdot \left(-\frac{m+1}{2}\right)_k}{\left(-\frac{m+n}{2}\right)_k \cdot \left(-\frac{m+n-1}{2}\right)_k}
$$
And thus, since $r(m_\ast) = 0$ we have
$$
   \mathcal{S}(n,m) = \binom{n+m}{n-1} \cdot {}_3F_2\left(\left.\begin{array}{cll} -n & -m/2 & -(m+1)/2 \\ & -(m+n)/2 & -(m+n-1)/2 \end{array} \right| 1 \right)
$$
Now, per this identity:
$$
  {}_3F_2\left(\left.\begin{array}{cll} -n & a & b \\ & d & 1+a+b-d-n \end{array} \right| 1 \right) = \frac{(d-a)_n \cdot (d-b)_n}{(d)_n \cdot (d-a-b)_n}
$$
Using this identity for $a = -m/2$, $b = -(m+1)/2$ and $d=\epsilon-(m+n)/2$ with the intent to consider the limit of $\epsilon \to 0$ we have
$$
   \mathcal{S}(n,m) = \binom{n+m}{n-1} \lim_{\epsilon \to 0} \frac{ \left(-\frac{n}{2} + \epsilon \right)_n \cdot \left(\frac{1}{2}-\frac{n}{2} + \epsilon \right)_n}{ \left(-\frac{m+n}{2} + \epsilon \right)_n \cdot \left(\frac{1}{2}-\frac{n-m}{2} + \epsilon \right)_n }
$$
Using
$$
   \left(-\frac{n}{2} + \epsilon \right)_n \cdot \left(\frac{1}{2}-\frac{n}{2} + \epsilon \right)_n = \frac{1}{2^{2n}} \frac{\Gamma(n+2 \epsilon)}{\Gamma(-n+2\epsilon)} = (-1)^n \frac{\Gamma(1+n-2\epsilon) \Gamma(n+2\epsilon)}{2^{2n} \pi} \sin(2 \pi \epsilon) 
$$
$$
 \left(-\frac{m+n}{2} + \epsilon \right)_n \cdot \left(\frac{1}{2}-\frac{n-m}{2} + \epsilon \right)_n = \frac{\Gamma\left(\frac{n-m}{2} + \epsilon\right) \Gamma\left(\frac{n+m+1}{2} + \epsilon\right) }{\Gamma\left(\frac{-n-m}{2} + \epsilon\right)\Gamma\left(\frac{1+m-n}{2} + \epsilon\right)} = \frac{\Gamma\left(\frac{n-m}{2} + \epsilon\right) \Gamma\left(\frac{n+m+1}{2} + \epsilon\right) }{-\frac{2\pi^2}{\sin(\pi m) + \sin(\pi n - 2 \pi \epsilon)}} \Gamma\left(1 + \frac{m+n}{2} - \epsilon\right) \Gamma\left( \frac{1+n-m}{2} - \epsilon\right) = (-1)^n \frac{\sin(2\pi \epsilon)}{2 \pi^2} \Gamma\left(\frac{n-m}{2} + \epsilon\right) \Gamma\left(\frac{n+m+1}{2} + \epsilon\right) \Gamma\left(1 + \frac{m+n}{2} - \epsilon\right) \Gamma\left( \frac{1+n-m}{2} - \epsilon\right)
$$
Combining, and using the duplication formula we get
$$
    \mathcal{S}(n,m) = \binom{n+m}{n-1} \frac{n! (n-1)!}{(n+m)! (n-m-1)!} = \binom{n}{m+1}
$$
A: Here is an elementary proof, which I found by studying finite difference operations, but finally formulates somewhat smoother using generating functions. As for the difference operation approach, it easily shows that for the usual definition of binomial coefficients the left hand side is always $0$. Indeed with $\Delta$ the difference operation defined by $(\Delta f)(x)=f(x+1)-f(x)$ one has
$$
  (\Delta^n f)(x)=\sum_{k=0}^n(-1)^{n-k}\binom nkf(x+k)
$$
and the left hand side matches this at $x=0$ for $f:x\mapsto(-1)^n\binom{n+m-2x}{n-1}$, which with the usual defintion of binomial coefficients is a polynomial function of degree $n-1$, so $\Delta^n f=0$.
So one must assume the summation in the question is supposed to be truncated when $n+m-2k$ becomes negative. This can be obtained by rewriting the left hand side in the question to
$$
  \sum_{k=0}^{n} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{m+1-2k},
$$
which makes the lower index negative whenever the upper index is, and with the usual definition of binomial coefficients a negative lower index makes them zero regardless. Now it turns out this is best interpreted using negative binomial powers, so let us make the upper index unconditionally negative by "negating the upper index" (making it $(m+1-2k)-(m+n-2k)-1=-n$):
$$
  \sum_{k=0}^{n} (-1)^{k}\binom{n}{k}(-1)^{m+1-2k}\binom{-n}{m+1-2k}.
$$
Now we see this is a certain convolution of the coefficients of $(1-X)^n$ and half of the coefficients of $(1-X)^{-n}=\sum_i(-1)^i\binom{-n}iX^i$, namely those whose parity is that of $m+1$. This is more conveniently described by making the left factor into a polynomial in $X^2$: the formula above describes the coefficient of $X^{m+1}$ in the power series (which turns out to be a polynomial)
$$
  (1-X^2)^n(1-X)^{-n}=((1-X)(1+X))^n(1-X)^{-n}=(1+X)^n.
$$
This coefficient is of course $\binom n{m+1}$.
Note that with the question reformulated properly, it works for any $n\in\mathbf N$ and $\def\Z{\mathbf Z}m\in\Z$.
Here's a description purely in terms of difference operators. The expression in the question naturally leads to considering the sequence $\binom k{n-1}_{k\in\mathbf N}$ and repeatedly taking differences of element two places apart. For simplicity extend the sequence by terms $0$ to the left so that it is indexed by $\Z$, and define the right-shift operator $R$ on sequences $f$ by $R(f)_i=f_{i-1}$ for all $i\in\Z$; using it define the "backward difference by $2$" operator $\nabla_2=I-R^2:f\mapsto(f_i-f_{i-2})_{i\in\Z}$. Now $I$ and $R$ commute, so applying the binomial formula to $(I-R^2)^n$ gives $\nabla_2^n(f)_k=\sum_{k=0}^n(-1)^n\binom nkf_{i-2k}$. In order to interpret the left hand side in the question as such an iterated difference, define sequences $C^{(k)}$ to be "column $k$" of Pascal's triangle shifted so as to start with a $1$, and $0$-extended to the left:
$$
  C^{(k)}_i=\begin{cases}\binom{k+i}k&\text{if $i\geq0$}\\
                         0&\text{if $i<0$;}\end{cases}
$$
then we are asked to prove that
$$
  \nabla_2^n(C^{(n-1)})_{m+1}=\binom n{m+1}.
$$
Now observe that with $\nabla_1=I-R$ one has $\nabla_1(C^{(k)})=C^{(k-1)}$ for all $k>0$, and $\nabla_1(C^{(0)})=D=(\delta_{i,0})_{i\in\Z}$, the sequence with a single nonzero term $1$ at index $0$ (this is where the truncation of negative index terms really kicks in). This suffices for computing $\nabla_1^n(C^{(n-1)})$, but we need the same with $\nabla_2$ instead of $\nabla_1$. Fortunately $\nabla_2=(1-R^2)=(1+R)(1-R)=(1+R)\nabla_1$, and everything commutes, so
$$
 \nabla_2^n(C^{(n-1)})=(1+R)^n(\nabla_1^n(C^{(n-1)}))
  =(1+R)^n(D)=\binom ni_{i\in\Z}.
$$
Evaluating this at index $i=m+1$ gives $\binom n{m+1}$, as desired.
A: Sledgehammer is Gosper summation... see Petkovsek, Wilf, Zeilberger "A = B". That works, guaranteed. Most computer algebra packages implement this.
Otherwise I'd grab Graham, Knuth, Patashnik "Concrete mathematics", techniques to handle such sums by clever index manipulation are clearly explained there.
Another venue would be Wilf's "snake oil method" (see his "generatingfunctionology").
A: Suppose we seek to evaluate
$$\sum_{k=0}^{\lfloor (m+n)/2 \rfloor}
{n\choose k} (-1)^k {m+n-2k\choose n-1}.$$
As the link in the OP seems no longer to be working I present the complex variable proof.
Observe  that  in  the   second  binomial  coefficient  we  must  have
$m+n-2k\ge  n-1$ in  order  to avoid  hitting  the zero  value in  the
product in  the numerator  of the binomial  coefficient, so  the upper
limit for the sum is in fact $m+1\ge 2k$ with the sum being
$$\sum_{k=0}^{\lfloor (m+1)/2 \rfloor}
{n\choose k} (-1)^k {m+n-2k\choose n-1}.$$
Introduce
$${m+n-2k\choose n-1} = {m+n-2k\choose m+1-2k}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+n-2k}}{z^{m+2-2k}} \; dz.$$
This integral correctly encodes the  range for $k$ being zero when $k$
is larger than $\lfloor (m+1)/2 \rfloor.$ Therefore we may let $k$ go
to infinity in the sum and obtain for $n\gt m$
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+n}}{z^{m+2}} 
\sum_{k\ge 0} {n\choose k} (-1)^k \frac{z^{2k}}{(1+z)^{2k}}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+n}}{z^{m+2}} 
\left(1-\frac{z^2}{(1+z)^2}\right)^n
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{(1+z)^{n-m} z^{m+2}} 
(1+2z)^n \; dz.$$
This produces the closed form
$$\sum_{q=0}^{m+1} {n\choose q} 2^q (-1)^{m+1-q}
{m+1-q+n-m-1\choose n-m-1}
\\ = (-1)^{m+1} \sum_{q=0}^{m+1} {n\choose q} (-1)^q 2^q
{n-q\choose n-m-1}.$$
This is
$$(-1)^{m+1} \sum_{q=0}^{m+1} {n\choose q} (-1)^q 2^q
{n-q\choose m+1-q}.$$
Introduce
$${n-q\choose m+1-q} 
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n-q}}{z^{m+2-q}} \; dz$$
which once  more correctly  encodes the range  with the pole  at $z=0$
disappearing when $q\gt m+1.$ Therefore we may extend the range to $n$
to get
$$\frac{(-1)^{m+1}}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{m+2}} 
\sum_{q=0}^{n} {n\choose q} (-1)^q 2^q \frac{z^q}{(1+z)^q}
\; dz
\\ = \frac{(-1)^{m+1}}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{m+2}} 
\left(1-2\frac{z}{1+z}\right)^n \; dz
\\ = \frac{(-1)^{m+1}}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{m+2}} 
\frac{(1-z)^n}{(1+z)^n} \; dz
\\ = \frac{(-1)^{m+1}}{2\pi i}
\int_{|z|=\epsilon} \frac{(1-z)^{n}}{z^{m+2}} \; dz
\\ = (-1)^{m+1} {n\choose m+1} (-1)^{m+1}
= {n\choose m+1}.$$
