A sum of a product of binomial coefficients: $\sum^{n}_{i=0}{(-1)^{i}\binom{n}{ i}\binom{n +m - i}{j-i}}$ I am supposed to manipulate the equation $\sum^{n}_{i=0}{(-1)^{i}\binom{n}{ i}\binom{n +m - i}{j-i}}$, where n,m,j are natural numbers and $n \leq j \leq n+m$ into something without a sum.
The only comment is to interpret this combinatorially and use the Principle of Inclusion and Exclusion.
I have tried writing out the binomial coefficients, but to no avail. Combinatorially I am lost as well.
I have no idea on how to proceed. Any help would be greatly appreciated.
 A: Here is an answer using generating functions. We seek to evaluate
$$\sum_{k=0}^n {n\choose k} (-1)^k {n+m-k\choose j-k}$$
where $n\le j \le n+m.$
Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the product of the two generating functions is the generating function of
$$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
Now we need to bring the given sum into the right format. We get
$$\frac{1}{(n+m-j)!}
\sum_{k=0}^n {n\choose k} \frac{(-1)^k}{(j-k)!} (n+m-k)!$$
This gives for $A(z)$ that
$$A(z) = \sum_{k\ge 0} \frac{(-1)^k}{(j-k)!} \frac{z^k}{k!}
= \frac{1}{j!} \sum_{k\ge 0} {j\choose k} (-z)^k
= \frac{1}{j!} (1-z)^j.$$
For $B(z)$ we get that
$$B(z) = \sum_{k\ge 0} (k+m)! \frac{z^k}{k!}
= m! \sum_{k\ge 0} {k+m\choose k} z^k = m! \frac{1}{(1-z)^{m+1}}.$$
Therefore the closed form of the sum is given by
$$\frac{1}{(n+m-j)!} n! [z^n] A(z) B(z) =
\frac{1}{(n+m-j)!} n! [z^n] \frac{m!}{j!} \frac{1}{(1-z)^{m+1-j}}$$
This is
$$\frac{1}{(n+m-j)!} n! \frac{m!}{j!} {n+m-j\choose n}
= \frac{1}{(n+m-j)!} n! \frac{m!}{j!} \frac{(n+m-j)!}{n!(m-j)!}
= {m\choose j},$$
QED. I do think the mechanics of this calculation make it attractive.
There is another calculation of this type at this MSE link -- I and at this MSE link -- II.
A: My hunch was wrong, it has to do with the exclusion-inclusion principle. Consider a set of $n+m$ elements (labeled $1,2,... n+m$) Define the set $S$ as the set of all subsets of $S$ with $j$ elements (ignoring the ordering), such set has cardinality $|S| = \binom{n+m}{j}$, an element of $S$ looks something like $(1,3,4,9,\cdots, \cdot)$ with $j$ numbers inside. Now, let $A_k$ be the subset of $S$ given by all elements of $S$ which contain the number $k$, we let this number take the values $k=1,2, \cdots, n$, since repetitions are not allowed, and all possible collections are counted, the cardinality of such set is easily computed by fixing one element to be $k$, leaving $j-1$ slots to fill, from $n+m-1$ numbers, hence:
$|A_k| = \binom{n+m-1}{j-1}$
There are $n$ such sets 
It is easy also to show that (using the same argumentation, now two numbers are fixed $k,l$ with $k\neq l$ so there remain $j-2$ slots to be filled with $n+m-2$ numbers)
$|A_k \cap A_l| = \binom{n+m-2}{j-2} $
In general now we have
$$|\bigcap_{a=1}^i A_{l_a} | =\binom{n+m-i}{j-i} $$
and there are $\binom{n}{i}$ such intersections (all sets carry $i$ distinct subindices). The exclusion inclusion principle is now applied to the set $S$ and the subsets $A_i$ this is just substitution:
$$ 
|S - \bigcup_{i=1}^n A_i| = \sum_{i=0}^n (-1)^i \binom{n}{i} \binom{n+m-i}{j-i}
$$
Compute now the cardinality of the set directly: it is the subset of elements of $S$ which do not contain any of the numbers $1,2, \cdots, n$, so these are all the combinations of just $m$ numbers in $j$ slots. This number is $\binom{m}{j}$, so we conclude that:
$$
\sum_{i=0}^n (-1)^i \binom{n}{i} \binom{n+m-i}{j-i} = \binom{m}{j}
$$
