Combinatorics – Proving a Binomial Coefficient Summation Formula

algebra-precalculusbinomial theorembinomial-coefficientscombinatoricssummation

I am trying to prove the following binomial identity:

$$\sum_{i=0}^n (-1)^i\binom{n}{i}\binom{m+i}{m}=(-1)^n\binom{m}{m-n}$$

My idea was to use the identity
$$\binom{m}{m-n}=\binom{m}{n}=\sum_{i=0}^n(-1)^i \binom{m+1}{i}$$ but the coefficients of the two sums don't seem to be equal.

I also know there is a combinatorial argument that proves this, but I am trying to find an algebraic proof.

Best Answer

We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{i=0}^n}&(-1)^i\binom{n}{i}\binom{m+i}{m}\\ &=\sum_{i=0}^{n}(-1)^i\binom{n}{i}[z^m](1+z)^{m+i}\tag{2}\\ &=[z^m](1+z)^m\sum_{i=0}^n\binom{n}{i}(-1)^i(1+z)^i\tag{3}\\ &=[z^m](1+z)^m\left(1-(1+z)\right)^n\tag{4}\\ &=[z^m](1+z)^m(-z)^n\\ &=(-1)^n[z^{m-n}](1+z)^m\tag{5}\\ &\,\,\color{blue}{=(-1)^n\binom{m}{m-n}}\tag{6} \end{align*}

Comment:

  • In (2) we apply the coefficient of operator according to (1).

  • In (3) we factor out terms independent from $i$.

  • In (4) we apply the binomial theorem.

  • In (5) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$>

  • In (6) we apply (1) again.

Note: This method is referred to as Egorychev I in the publication Egorychev Method: A Hidden Treasure by M. Riedel and H. Mahmoud.

Related Question