Sum of product of binomial coefficients: $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n$ 
Based on the binomial expansion of $(1+x)^n$, show that:
$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n.$$

This is a question from a very old high school exam paper I came across. It looks like it involes the product of two binomial expansions but I cannot figure this out. Any help much appreciated.
 A: If you write the equation to prove as $\sum_k(-1)^{n-k}\binom nk\binom{n+k}n=1$, you can interpret the left hand side as the result of applying the $n$-th finite difference operation $\Delta^n$ to the sequence $k\mapsto\binom kn$, and taking the term of the resulting sequence at $k=n$. Then $\Delta(k\mapsto\binom km)=k\mapsto\binom k{m-1}$ implies that the left hand side becomes $\Delta^n\left(k\mapsto\binom kn\right)(n)=\binom n{n-n}=\binom n0=1$ as desired.
Another approach is to recognise negation of the upper index in the second binomial coefficient:
$$
  (-1)^k\binom{n+k}k=\binom{k-(n+k)-1}k=\binom{-n-1}k,
$$
after which the identity becomes in instance of the Vandermonde identity
$$
\sum_{k=0}^n(-1)^k\binom nk\binom{n + k}k=
\sum_k\binom n{n-k}\binom{-n-1}k=\binom{-1}n=(-1)^n.
$$
${}$
Added after request in comment. Neither of these arguments requires much beyond basic knowledge about binomial coefficients. The difference operator $\Delta$ is defined by $\Delta(f)(k)=f(k+1)-f(k)$, so with $f:k\mapsto\binom km$ one gets
$$
  \Delta(f)(k)=\binom{k+1}m-\binom km=\binom k{m-1}
$$
just from Pascal's recurrence. And the formula
$$
  \Delta^n(f)(n)=\sum_i(-1)^{n-i}\binom nif(n+i)
$$
either follows easily by induction from the definition of $\Delta$, or if you prefer by using the operators identity $I$ and shift $S$ on functions, defined by $I(f)=f$ and $S(f)(i)=f(i+1)$, writing $\Delta=S-I$, and using the binomial formula for $(S-I)^n$ (possible since $S$ and $I$ commute).
In the second variant, you probably already know the formula $\binom{-n}k= (-1)^k\binom{n+k-1}k$ for binomial coefficients with negative upper index, or else the equality between the outer expressions in
$$
  (1+X)^{-n} = \sum_{k\in\mathbf N} \binom{-n}kX^k
  = \sum_{k\in\mathbf N}(-1)^k\binom{n+k-1}kX^k
$$
(if not, see this answer deriving the first formula). Then $\sum_k(-1)^k\binom{n+k}kX^k=(1+X)^{-n-1}$, and the instance of the Vandermonde identity is proved by comparing coefficients in
$$
 \sum_n\left(\sum_{k=0}^n(-1)^k\tbinom{n + k}k\tbinom nk\right)X^n
 =(1+X)^{-n-1}(1+X)^n=(1+X)^{-1}=\sum_n(-1)^nX^n
$$
which might be the proof using only manipulation of $(1+X)^{n-1}$ you asked for.
A: Suppose we seek to evaluate
$$\sum_{k=0}^n (-1)^k {n\choose k} {n+k\choose k}.$$
Start from
$${n+k\choose k}
= \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{n+k} \; dz.$$
This yields the following expression for the sum
$$\frac{1}{2\pi i} 
\int_{|z|=\epsilon}
\sum_{k=0}^n {n\choose k}
\frac{(-1)^k}{z^{k+1}} (1+z)^{n+k} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{(1+z)^n}{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{(1+z)^n}{z}
\left(1-\frac{z+1}{z}\right)^n \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{(1+z)^n}{z}
\frac{(-1)^n}{z^n} \; dz
\\ = \frac{(-1)^n}{2\pi i} 
\int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}}\; dz.$$
It follows that the closed form of the sum is given by
$$(-1)^n [z^n] (1+z)^n = (-1)^n.$$
A trace as to when this method appeared on MSE and by whom starts at this
MSE link.
A: The following combinatorial proof may be of interest as well. After multiplying both sides by $(-1)^n$, and reindexing the summation by replacing $k$ with $n-k$, we can rewrite the equation to be proved as
$$
\sum_{k=0}^n(-1)^k\binom{n}k\binom{2n-k}n=1
$$
Both sides are answer to the following question:

How many strings of $n$ ones and $n$ zeroes are there were no zero is immediately followed by a one?

Obviously, there is only one such string, $11\cdots100\cdots0$.
On the other hand, we can count this using the principle of inclusion exclusion. Take all of the $\binom{2n}n$ strings of $n$ zeroes and $n$ ones, and for each $i=1,2,\dots,n$, subtract the strings where the $i^{th}$ zero is followed by a ones. Every such string can be generated by taking an arbitrary string of $n$ zeroes and only $n-1$ ones, then adding a one after the $i^{th}$ zero. Therefore, for each $i=1,\dots,n$, we must subtract $\binom{2n-1}n$, so subtract $n\binom{2n-1}n$. 
However, strings with two instances of a zero followed by a one have been double subtracted, so these must be added back in. Using a similar method, the number strings where both the $i^{th}$ zero and the $j^{th}$ zero are followed by ones is $\binom{2n-2}n$. We must add this for each of the $\binom{n}2$ pairs of zeroes, so add in $\binom{n}2\binom{2n-2}n$. 
Continuing in this fashion (subtracting in the triply subtracted strings, adding in the quadruply subtracted strings, etc), we recover the alternating sum on the left hand side.
A: Just for seeing a direct method:
$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k}= \sum_{k=0}^{n}\binom{n}{n-k}\binom{-n-1 }{k} $$$$=\binom{-1 }{n}=\left(-1\right)^{n}\binom{n}{n}=\left(-1\right)^{n}$$
