How can I transform the following sum s.t. one can apply the Vandermonde convolution and thus obtain a solution for this summation?

$$ \sum_{k \leq n} \binom{n-k} r \binom m {k-s} (-1)^k,\quad \text{integers } n, r, s\ge 0 $$

I thought about this a bit but don't even get how we can pull the $(-1)^k$ into the binomial coefficient or how to swap the arguments of the first coefficient.


1 Answer 1


\begin{align*} &\sum_{k\le n} \binom{n-k}{r} \binom{m}{k-s} (-1)^k \stackrel{(1)}{=} \sum_{k\le n} \binom{n-k}{n-k-r} \binom{m}{k-s} (-1)^k \\[10pt] \stackrel{(2)}{=} {} & \sum_{j\ge -r} \binom{n-(-j+n-r)}{j} \binom{m}{n-r-j-s} (-1)^{n-r-j} \\[10pt] = {} & \sum_{j\ge -r} \binom{j+r}{j} \binom{m}{(n-r-s)-j} (-1)^{n+r-j} \\[10pt] \stackrel{(3)}{=} {} & \sum_{j\ge -r} \binom{-r-1}{j} \binom{m}{(n-r-s)-j} (-1)^{n+r} \stackrel{(4)}{=} (-1)^{n+r} \binom{m-r-1}{n-r-s}. \end{align*}

$(1)$ Symmetry of the binomial coefficient

$(2)$ Change of index $j=n-k-r$

$(3)$ Upper negation identity: $$ \binom{n}{k}=(-1)^k \binom{k-n-1} k $$

$(4)$ Vandermonde convolution


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .