Curious Binomial Coefficient Identity Consider the following set of identities:  ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ...
This set of identities can be written as
$${m+1\choose k}=1+\sum_{i=0}^{k-1}(-1)^i{k\choose i+1}{m-i\choose k}\tag 1$$
or alternatively as
$$\sum_{i=0}^k(-1)^i{k\choose i}{m-i\choose k}=1$$
Interestingly, the form in $(1)$ suggests that every binomial coefficient can be written as a recurrence in only terms from its own line (ignoring the $k\choose i+1$ terms as "predetermined constants"):
$$a_{n+1}=1+\sum_{i=0}^{k-1}(-1)^i{k\choose i+1}a_{n-i}$$
What is the best way to prove these identities hold in general?  The proofs for $k=1,2,3$ were very straightforward with simple factorial expansion, but even induction doesn't seem to be working in the general case.
Also, do these identities have a name?
These identities appeared as I was considering the quantity
$$\frac{x^n+y^n}{x+y}\pmod{(x+y)^k}$$
 A: Here's an approach via generating functions (it is possible to make the proof shorter by avoiding them, but this was the straightforward approach without much cleverness).
If you have 
$$A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$$
and
$$B(x) = b_0 + b_1x + b_2 x^2 + b_3x^3 + \dots$$
(the objects $A(x)$ and $B(x)$ are called generating functions of the two sequences) then their product
$$A(x)B(x) = C(x) = c_0 + c_1x + c_2x^2 + c_3x^3+\dots$$
satisfies
$$c_n = \sum_{r = 0}^{n} a_r b_{n-r}.$$
When, for some fixed $k$, the sequences are $a_n = (-1)^n\binom{k}{n}$ and $b_n = \binom{n}{k}$, we have 
$$A(x) 
= \sum_{n=0}^{\infty}(-1)^n\binom{k}{n}x^n
= (1 - x)^k
$$
and
$$B(x)
= \sum_{n=0}^{\infty}\binom{n}{k}x^n = \frac{x^k}{(1-x)^{k+1}}
$$
(see here; this is a good exercise) so that their product is
$$C(x) = A(x)B(x) = (1-x)^k \frac{x^k}{(1-x)^{k+1}} = \frac{x^k}{1-x} = x^k(1 + x + x^2 + \dots)$$
for which we have, for $n \ge k$, 
$$1 = c_n = \sum_{r=0}^{n}a_{r} b_{n-r} 
= \sum_{r=0}^n (-1)^r \binom{k}{r}\binom{n-r}{k}
= \sum_{i=0}^k (-1)^i \binom{k}{i}\binom{n-i}{k}
$$
(as $\binom{k}{r} = 0$ for $r > k$) which is what you wanted to prove.
A: As usual let $[m]=\{1,\ldots,m\}$; we’ll count the $k$-sized subsets of $[m]$ that are contained in $[k]$. On the one hand there is obviously exactly one such set, namely, $[k]$ itself. On the other hand, for each $i\in[k]$ let $A_i$ be the family of $k$-sized subsets of $[m]$ that do not contain $i$. For any $I\subseteq[k]$ we have
$$\left|\bigcap_{i\in I}A_i\right|=\binom{m-|I|}k\;,$$
so a straightforward inclusion-exclusion argument shows that
$$\left|\bigcup_{i=1}^kA_i\right|=\sum_{i=1}^k(-1)^{i+1}\binom{k}i\binom{m-i}k$$
and hence that 
$$1=\binom{m}k-\left|\bigcup_{i=1}^kA_i\right|=\sum_{i=0}^k(-1)^i\binom{k}i\binom{m-i}k\;.$$
A: Here is the usual complex variables proof. Suppose we seek to show that
$$\sum_{k=0}^n {n\choose k} (-1)^k {m-k\choose n} = 1$$
Introduce the integral representation
$${m-k\choose n}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{m-k}}{z^{n+1}}
\; dz.$$
This gives for the sum the integral
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{m}}{z^{n+1}}
\sum_{k=0}^n {n\choose k} (-1)^k \frac{1}{(1+z)^k}\; dz$$
or
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{m}}{z^{n+1}}
\left(1-\frac{1}{1+z}\right)^n \; dz
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{m}}{z^{n+1}}
\left(\frac{z}{1+z}\right)^n \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{m-n}}{z} \; dz.$$
Now this evaluates to one by inspection, since we have an ordinary binomial when $m\ge n$ and a Newton binomial which starts at one when $m<n.$ (Observe that we need the constant coefficient.)
A: For completeness, I did manage to create an inductive argument for this identity, though it is nowhere near the simplicity and elegance of the others here.  I have also found a much simpler argument using finite differences; I'll leave the induction argument intact below the argument by polynomial theory:
Let $p(x)$ be a given integer-valued polynomial of degree $d$.  The $n$th forward finite difference is given by
$$\Delta_p^n(x)=\sum_{i=0}^n(-1)^i{n\choose i}p(x+i)$$
If $n=d$ we get a constant, namely, the leading coefficient of $p(x)$ as taken in binomial form, i.e., $p(x)=\sum_ia_i{x\choose i}$.  The formula stated in the question is an immediate consequence of these facts, taking $p(x)=\binom xn$.
Here is the proof by induction for anyone who might be interested:
For proof of $(1)$, use strong induction and start with $\binom {n+1}1 = 1 + \sum_{i=0}^{1-1}(-1)^i{k\choose i+1}{n-i\choose k} = 1+\binom n1 = n+1$.  Assuming for $k = q$, we get
$${n+1\choose q} = 1+\sum_{i=0}^{q-1}(-1)^i{q\choose i+1}{n-i\choose q}$$
Establishing a base-case for $k=q+1$ is a matter of considering
$${q+2\choose q+1}=q+2 = 1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{q+1-i\choose q+1}=1+q+1 = q+2$$
after which we again make an assumption that our formula holds, this time for $n=r, r\ge q+1$:  ${r+1\choose q+1}=1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r-i\choose q+1}$.  All that remains is to test the formula for $n=r+1$:
$$\begin{align}{r+2\choose q+1} &= 1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}\\
 &= {r+1\choose q+1}+{r+1\choose q}\end{align}$$
By strong induction, we can use the formulas for $r+1\choose q+1$ and $r+1\choose q$ and write
$$\begin{align}{r+1\choose q+1}+{r+1\choose q}&=2+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r-i\choose q+1}+\sum_{i=0}^{q-1}(-1)^i{q\choose i+1}{r-i\choose q}\\
&=2+(-1)^q{r-q\choose q+1}+\sum_{i=0}^{q-1}(-1)^i\left({q+1\choose i+1}{r-i\choose q+1}+{q\choose i+1}{r-i\choose q}\right)\end{align}$$
This is a bit messy, but it works out well:
$$\begin{align}{q+1\choose i+1}{r-i\choose q+1}+{q\choose i+1}{r-i\choose q}&={q+1\choose i+1}{r-i\choose q+1}+\left[{q+1\choose i+1}-{q\choose i}\right]{r-i\choose q}\\
&={q+1\choose i+1}\left[{r-i\choose q+1}+{r-i\choose q}\right]-{q\choose i}{r-i\choose q}\\
&={q+1\choose i+1}{r-i+1\choose q+1}-{q\choose i}{r-i\choose q}\end{align}$$
Going in reverse, we now have
$$\begin{align}{r+1\choose q+1}+{r+1\choose q}&=2+(-1)^q{r-q\choose q+1}+\sum_{i=0}^{q-1}(-1)^i\left({q+1\choose i+1}{r+1-i\choose q+1}-{q\choose i}{r-i\choose q}\right)\\
&=2+(-1)^q{r-q+1\choose q+1}-(-1)^q{r-q\choose q}+\sum_{i=0}^{q-1}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-\sum_{i=0}^{q-1}(-1)^i{q\choose i}{r-i\choose q}\\
&=2+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-\sum_{i=0}^{q}(-1)^i{q\choose i}{r-i\choose q}\\
&=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-{r\choose q}+1-\sum_{i=1}^{q}(-1)^i{q\choose i}{r-i\choose q}\\
&=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-{r\choose q}+1+\sum_{j=0}^{q-1}(-1)^j{q\choose j+1}{r-j-1\choose q}\\
{r+2\choose q+1}&=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}\end{align}$$
Note that the last step follows from strong induction due to the original formula (with $r\ge q+1$)
$$\binom rq = 1+\sum_{i=0}^{q-1}{q\choose i+1}{r-1-i\choose q}$$
A: $$\begin{align}
\sum_{i=0}^k(-1)^i {k\choose i} {m-i\choose k}
&=\sum_{i=0}^k(-1)^i {k\choose i} {m-i\choose m-k-i}\\
&=\sum_{i=0}^k (-1)^i{k\choose i }{-k-1\choose m-k-i}(-1)^{m-k-i}&&(1)\\
&=(-1)^{m-k}\sum_{i=0}^k {k\choose i }{-k-1\choose m-k-i}\\
&=(-1)^{m-k}{-1\choose m-k}&&(2)\\
&=(-1)^{m-k}{m-k\choose m-k}(-1)^{m-k}&&(3)\\
&=1\qquad\blacksquare\end{align}$$
(1): Upper Negation
(2): Vandermonde
(3): Upper Negation
