Binomial Fever!

We're looking for $\sum_{k=0}^n (-1)^k \binom{n}{k}\binom{2n-k}{n},$ which is the coefficient of $x^n$ in the product $\left( \sum_{c=0}^\infty (-1)^c \binom{n}{c} x^c \right) \left( \sum_{d=0}^\infty \binom{n+d}{n} x^d \right)$ (take $c=k, d=n-k$ ).

The first sum is $(1-x)^n,$ and the second sum is $\frac1{(1-x)^{n+1}}.$ (This can be derived by starting with the geometric series for $\frac1{1-x}$ and repeatedly taking derivatives of both sides.)

So the product is $\frac1{1-x} = \sum\limits_{k=0}^\infty x^k,$ and the coefficient of $x^n$ is always $\fbox{1}.$

The given expression is equivalent to finding the coefficient of $x^n$ in the following expression:

$\binom{n}{0}(1+x)^{2n}-\binom{n}{1}(1+x)^{2n-1}+\binom{n}{2}(1+x)^{2n-2}-\cdots +(-1)^n\binom{n}{n}(1+x)^n$

That is in the following expression:

$[1+x]^n[\binom{n}{0}(1+x)^{n}-\binom{n}{1}(1+x)^{n-1}+\binom{n}{2}(1+x)^{n-2}-\cdots+(-1)^n\binom{n}{n}]$

That is in the following expression:

$-[1+x]^n[1-(1+x)]^n=-[1+x]^n[-x]^n$ (Because n is odd in this case)

Which is clearly 1 as all the terms in $[1+x]^n$ except the constant term will give powers greater than $n$ on multiplying with $(-x)^n$

This is longer than the other solutions.

Suppose we have n boys and n girls. We choose a team of n farmers, and some (or possibly 0) pirates, where only boys are allowed to be pirates.

The number of ways to do this if there are k pirates is $\binom{n}{k} \binom{2n-k}{n}$ .

So the sum we seek is the number of selections with an even number of pirates, minus the number of selections with an odd number of pirates.

Suppose not all boys are farmers, then the oldest non-farmer boy can switch from being a pirate to not being a pirate or visa-versa. This gives a bijection between selections with an odd number of pirates and selections with an even number of pirates where not all boys are pirates.

There is 1 selection where all boys are farmers (and there are therefore 0 pirates)

So the difference between the number of selections with an even number of pirates and the number of selections with an odd number of pirates is 1.