Using generating functions to solve binomial identities

Question

I would like to solve the two identities, $$\sum_{j=0}^m \binom{n+j-1}{n-1} = \binom{n+m}{n}$$ $$\sum_{j=0}^m (-1)^{m-j} \binom{n+1}{m-j} \cdot \binom{n+j}{n} = 0$$ I was able to convince myself they are true using other methods, and now I am interested in a derivation using generating functions. How might I approach these problems?

Answer 1

We can do these using coefficient extractors which uses generating functions and sometimes, complex variables. For the first one we find

$$\sum_{j\ge 0} {n+j-1\choose n-1} [[j\le m]] = \sum_{j\ge 0} {n+j-1\choose n-1} [z^m] \frac{z^j}{1-z} \\ = [z^m] \frac{1}{1-z} \sum_{j\ge 0} {n+j-1\choose n-1} z^j = [z^m] \frac{1}{1-z} \frac{1}{(1-z)^{n}} \\ = [z^m] \frac{1}{(1-z)^{n+1}} = {n+m\choose n}.$$

We get for the second one

$$[z^m] (1+z)^{n+1} \sum_{j=0}^m (-1)^{m-j} z^j {n+j\choose n}.$$

Here the coefficient extractor enforces the upper range of the sum and we have

$$[z^m] (1+z)^{n+1} \sum_{j\ge 0} (-1)^{m-j} z^j {n+j\choose n} \\ = (-1)^m [z^m] (1+z)^{n+1} \frac{1}{(1+z)^{n+1}} = (-1)^m [z^m] 1 = 0.$$

This is for $m\ge 1.$ We learn at this point that we needed neither residues nor complex variables.

Answer 2

For the first $$ \eqalign{ & \sum\limits_{0 \le m} {\sum\limits_{j = 0}^m {\left( \matrix{ n + j - 1 \cr n - 1 \cr} \right)x^{\,j}\, y^{\,m} } } = \cr & \sum\limits_{0 \le m} {\sum\limits_{j = 0}^m {\left( \matrix{ n + j - 1 \cr j \cr} \right)x^{\,j} \, y^{\,m} \, } } = \cr & = \sum\limits_{0 \le j} {\sum\limits_{j \le m} {\left( \matrix{ - n \cr j \cr} \right)\left( { - x} \right)^{\,j} \, y^{\,m} } } = \cr & = \sum\limits_{0 \le j} {\sum\limits_{0 \le m - j} {\left( \matrix{ - n \cr j \cr} \right)\left( { - xy} \right)^{\,j} \, y^{\,m - j} } } = \cr & = {1 \over {\left( {1 - xy} \right)^{\,n} \left( {1 - y} \right)}}\;\;\buildrel {x = 1} \over \longrightarrow \;\;{1 \over {\left( {1 - y} \right)^{\,n + 1} }} = \cr & = \sum\limits_{0 \le m} {\left( \matrix{ n + m \cr n \cr} \right)y^{\,m} } = \sum\limits_{0 \le m} {\left( \matrix{ n + m \cr m \cr} \right)y^{\,m} } = \sum\limits_{0 \le m} {\left( \matrix{ - n - 1 \cr m \cr} \right)\left( { - y} \right)^{\,m} } \cr & \cr} $$ where:

• 1. symmetry ($0 \le n+j-1$);
• 2. upper negation ($0 \le n+j-1$);
• 3. change summation index ( $m \to m-j$)
• 4. sums are disjoint, and put $x=1$
• 5. sum over $y^m$ on the RHS.

Same track (more or less) for the second $$ \eqalign{ & \sum\limits_{0 \le m} {\sum\limits_{j = 0}^m {\left( { - 1} \right)^{\,m - j} \left( \matrix{ n + 1 \cr n - j \cr} \right)\left( \matrix{ n + j \cr n \cr} \right)x^{\,j} \, y^{\,m} \, } } = \cr & = \sum\limits_{0 \le m} {\sum\limits_{j = 0}^m {\left( { - 1} \right)^{\,j} \left( \matrix{ n + 1 \cr n - \left( {m - j} \right) \cr} \right)\left( \matrix{ n + m - j \cr m - j \cr} \right)x^{\,m - j} \, y^{\,m} \, } } = \cr & = \sum\limits_{0 \le m} {\sum\limits_{0 \le m - j} {\left( { - 1} \right)^{\,j} \left( \matrix{ n + 1 \cr n - \left( {m - j} \right) \cr} \right)\left( \matrix{ n + m - j \cr m - j \cr} \right)x^{\,m - j} \, y^{\,m} \, } } = \cr & = \sum\limits_{0 \le m} {\sum\limits_{0 \le k} {\left( { - 1} \right)^{\,m} \left( \matrix{ n + 1 \cr n - k \cr} \right)\left( \matrix{ - n - 1 \cr k \cr} \right)x^{\,k} \, y^{\,m} \, } } \;\buildrel {x = 1} \over \longrightarrow \; \cr & \to \left( \matrix{ 0 \cr n\, \cr} \right){1 \over {\left( {1 + y} \right)}} = \delta _{n,0} \cr} $$