Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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} $$
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.
