Prove this binomial identity using the following equality:

Question

Use the equation $\frac{(1-x^2)^n}{(1-x)^n} = (1+x)^n$ to prove the following identity:

$\displaystyle \sum_{k=0}^\frac{m}{2}(-1)^k{n\choose k}{n+m-2k-1\choose n-1}={m\choose n}$, $m\leqslant n$ and $m$ even

I am really at a loss for how to do this. Where did the $m$ and condition $m$ even come from?

Answer 1

The coefficient of $x^{m-2k}$ in $\displaystyle \frac{1}{(1-x)^n}$ is $\displaystyle \binom{n+m-2k-1}{n-1}$ and the coefficient of $x^{2k}$ in the binomial expansion of $(1-x^2)^n$ is $\displaystyle (-1)^{k}\binom{n}{k}$.

Together that gives you the coefficient of $x^m$ in the expansion of: $$(1-x^2)^n \times \frac{1}{(1-x)^n} = \sum\limits_{m=0}^{\infty} \left(\sum\limits_{k=0}^{[m/2]}(-1)^{k}\binom{n}{k}\binom{n+m-2k-1}{n-1}\right)x^m$$

On the other hand the coefficient of $x^m$ in $(1+x)^n$ is simply $\displaystyle \binom{n}{m}$.

Answer 2

Let me just briefly present a different generating function.

Suppose we seek to evaluate $$\sum_{k=0}^{\lfloor m/2\rfloor} {n\choose k} (-1)^k {m-2k+n-1\choose n-1}$$

where $m\le n$ and introduce $${m-2k+n-1\choose n-1} = {m-2k+n-1\choose m-2k} \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m-2k+1}} (1+z)^{m-2k+n-1} \; dz$$

which has the property that it is zero when $2k\gt m$ so we may set the upper limit in the sum to $n,$ getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{m+n-1} \sum_{k=0}^n {n\choose k} (-1)^k \frac{z^{2k}}{(1+z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{m+n-1} \left(1-\frac{z^2}{(1+z)^2}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{m-n-1} (1+2z)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{m}} \frac{1}{z(1+z)} \frac{(1+2z)^n}{(1+z)^n} \; dz.$$

Now put $$\frac{1+2z}{1+z} = u \quad\text{so that}\quad z = -\frac{u-1}{u-2},\; 1+z = -\frac{1}{u-2},\; \frac{1+z}{z} = \frac{1}{u-1},\; \\ \quad \frac{1}{z(1+z)} = \frac{(u-2)^2}{u-1} \quad\text{and}\quad dz = \frac{1}{(u-2)^2} \; du$$

to get for the integral

$$\frac{1}{2\pi i} \int_{|u-1|=\gamma} \frac{1}{(u-1)^m} \frac{(u-2)^2}{u-1} u^n \frac{1}{(u-2)^2} \; du \\ = \frac{1}{2\pi i} \int_{|u-1|=\gamma} \frac{1}{(u-1)^{m+1}} u^n \; du.$$

This is $$[(u-1)^m] u^n = [(u-1)^m] \sum_{q=0}^n {n\choose q} (u-1)^q = {n\choose m}.$$

This solution is more complicated than the obvious one but it serves to illustrate some aspects of the method.

Concerning the choice of $\epsilon$ and $\gamma$ the closest that the image of $|z|=\epsilon$ which is $1+\frac{z}{1+z}$, gets to one, is $\epsilon/(1+\epsilon)$ so that must be the upper bound for $\gamma.$ Taking $\epsilon=1/3$ and $\gamma = 1/5$ will work. Note also that $u= 1+z+\cdots$ makes one turn around one.