A summation identity

Question

I have encountered this identity in Page 616 of Mathematical Methods for Students of Physics and Related Fields (Second Edition) by Sadri Hassani: $$ \sum_{m = 0}^{n}\left(-1\right)^{m}\, {\left(\,{2n + 2m}\,\right)! \over \left(\,{n + m}\,\right)!\,\left(\,{n - m}\,\right)!\, \left(\,{2m}\,\right)!} = \left(\,{-4}\,\right)^n $$. I don't know how one can obtain it directly, however, I tried to prove it by induction.

Thus, for $n = 1$, the identity is valid. If we assume its validity for $n$, we have to show that

$\sum_{m = 0}^{n + 1} (-1)^m \frac{(2n + 2m + 2)!}{(n + m + 1)! (n - m + 1)! (2 m)!} = (-4)^{n + 1}$.

The thing that comes to one's mind is that to separate the ($n + 1$)th term in the left-hand side of the above, and write it as

$(-1)^{n + 1} \frac{(4n + 4)!}{(2n + 2)! (2n + 2)!} + \sum_{m = 0}^{n} (-1)^m \frac{(2n + 2m + 2)!}{(n + m + 1)! (n - m + 1)! (2 m)!}$,

which with a little simplification, it becomes

$(-1)^{n + 1} \frac{(4n + 4)!}{(2n + 2)! (2n + 2)!} + 2 \sum_{m = 0}^{n} (-1)^m \frac{(2n + 2m + 1) (2n + 2m)!}{(n - m + 1) (n + m)! (n - m)! (2 m)!}$.

It seems to me that one cannot simplify it more in order to be able to use the assumption; one could divide $\frac{2n + 2m + 1}{n - m + 1}$ but it doesn't seem to lead anywhere. Any help to proceed from here is appreciated!

Answer 1

Here is a very different kind of answer than what you want. This is a sum of hypergeometric terms, and therefore in principle your identity is algorithmic to verify.

If we let $S(n)$ be your sum, then Zeilberger's algorithm (with, say, SumTools[Hypergeometric][Zeilberger](S, n, m, E) in Maple) returns the result $$ [E + 4,\ {\frac {m \left( 2\,m-1 \right) \left( -1 \right) ^{m} \left( 2\,n+2\,m \right) !\, \left( 8\,n+6 \right) }{ \left( -n+m-1 \right) \left( n+m \right) !\, \left( n-m \right) !\, \left( 2\,m \right) !\, \left( 2\,{n}^{2}+3\,n+1 \right) }}], $$ where $E$ is the shift operator $ES(n) = S(n + 1)$. This signifies that $S(n)$ satisfies the recurrence $(E + 4) S(n) = 0$, i.e., $S(n + 1) = -4S(n)$. (The second part is to "verify" the results of the algorithm, if you were so inclined.) Since it is easy to check that $S(0) = 1$, it follows that $S(n) = (-4)^n$ for $n \geq 0$.

---

Here's a more human approach, though still not "directly" evaluating the sum. I liberally use generating functions - see generatingfunctionology for a nice introduction.

Note that your sum is $$S(n) = \sum_{k = 0}^n (-1)^k {2(n + k) \choose n + k} {n + k \choose n - k} = \sum_{k \leq n} (-1)^k {2(n + k) \choose n + k} {n + k \choose n - k}$$ for $n \geq 0$. If we shift the summation variable back by $n$, then $$S(n) = \sum_{k \leq 2n} (-1)^{k - n} {2k \choose k}{k \choose 2n - k}.$$

There is one obvious simplification to try here: $(-1)^k {2k \choose k} = 4^k {-1/2 \choose k}$, which gives

$$S(n) = (-1)^n \sum_{k \leq 2n} 4^k {-1/2 \choose k}{k \choose 2n - k}.$$

The remaining hard part is the sum. The $2n$ is unimportant now (only $2n$ appears in the sum, never $n$ by itself), so let's define

$$R(n) = \sum_{k \leq n} 4^k {-1/2 \choose k} {k \choose n - k}.$$

If we have $R(n)$, then $S(n) = (-1)^n R(2n)$. [There is probably an easy way to evaluate $R(n)$, but I haven't found it yet.]

Let's stop thinking so hard, define $$R(x) = \sum_{n \geq 0} R(n) x^n,$$ and blindly manipulate some sums:

\begin{align*} R(x) &= \sum_{n \geq 0} \sum_{k \leq n} 4^k {-1/2 \choose k} {k \choose n - k} x^n \\ &= \sum_{k \geq 0} \sum_{n \geq k} 4^k {-1/2 \choose k} {k \choose n - k} x^n \\ &= \sum_{k \geq 0} 4^k {-1/2 \choose k} \sum_{n \geq k} {k \choose n - k} x^n \\ &= \sum_{k \geq 0} 4^k {-1/2 \choose k} \sum_{n \geq 0} {k \choose n} x^{n + k} \\ &= \sum_{k \geq 0} 4^k {-1/2 \choose k} x^k (1 + x)^k \\ &= \sum_{k \geq 0} [4x(1 + x)]^k {-1/2 \choose k} \\ &= (1 + 4x(1 + x))^{-1/2} \\ &= \frac{1}{1 + 2x} \\ &= \sum_{n \geq 0} (-2)^n x^n. \end{align*}

Therefore $R(n) = (-2)^n$, which finally gives $S(n) = (-1)^n R(2n) = (-4)^n$.

Answer 2

Introductory remark. The proof that I show below is not the simplest possible, but it does illustrate residue techniques. Seeing that we have two very different methods documented on the page it almost became a challenge whether we could prove it by residues, thereby adding a third method, for a Rosetta stone effect. The heart of the proof is in the first half, the second half is concerned with proving that a certain pole does not contribute to the count. Possibly this part can be simplified. It is hoped that the reader may gain by this additional perspective on this interesting sum.

We seek to show that

$$\sum_{m=0}^n (-1)^m {2n+2m\choose n+m} {n+m\choose n-m} = (-1)^n 2^{2n}.$$

The LHS is

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

The coefficient extractor enforces the upper limit of the sum and we may continue with

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \sum_{m\ge 0} (-1)^m {2n+2m\choose n+m} (1+z)^m z^m \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{(1-w)^{n+1}} \\ \times \sum_{m\ge 0} (-1)^m \frac{1}{w^m} \frac{1}{(1-w)^m} (1+z)^m z^m \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{(1-w)^{n+1}} \frac{1}{1+z(1+z)/w/(1-w)} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n}} \frac{1}{(1-w)^{n}} \frac{1}{w(1-w)+z(1+z)} \; dw \; dz \\ = - \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n}} \frac{1}{(1-w)^{n}} \frac{1}{(w+z)(w-(1+z))} \; dw \; dz.$$

The contribution from the pole at $w=-z$ is

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{(-1)^n}{z^{n}} \frac{1}{(1+z)^{n}} \frac{1}{1+2z} \; dz \\ = \frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} \frac{1}{1+2z} \; dz = (-1)^n [z^{2n}] \frac{1}{1+2z} = (-1)^n (-1)^{2n} 2^{2n} \\ = \bbox[5px,border:2px solid #00A000]{ (-1)^n 2^{2n}.}$$

This is the claim. We will document a choice of $\gamma$ and $\epsilon$ so that $w=0$ and $w=-z$ are the only poles inside the contour (pole at $w=1$ not included, nor the pole at $w=1+z.$)

Now we have for the pole at $w=0$

$$-\frac{1}{(w+z)(w-(1+z))} = \frac{1}{1+2z} \frac{1}{w+z} - \frac{1}{1+2z} \frac{1}{w-(1+z)} \\ = \frac{1}{z} \frac{1}{1+2z} \frac{1}{1+w/z} + \frac{1}{1+z} \frac{1}{1+2z} \frac{1}{1-w/(1+z)}.$$

We get from the first piece

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

The second piece yields

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

We see that the two pieces from $w=0$ cancel so that the contribution is zero. This almost completes the proof, we only need to choose the contour so that $w=1$ and $w=1+z$ are not included. For the initial geometric series to converge we need $|1+z|\epsilon\lt |1-w|\gamma.$ With $\epsilon$ and $\gamma$ in a neigborhood of zero we have $|1+z|\epsilon \le (1+\epsilon)\epsilon$ and $(1-\gamma)\gamma \le |1-w|\gamma.$ The series converges if $(1+\epsilon)\epsilon \lt (1-\gamma)\gamma.$ Therefore a good choice is $\epsilon = 1/10$ and $\gamma=1/5.$ The contour in $\gamma$ clearly includes $w=0$ and $w=-z$ and definitely does not include $w=1$ and $w=1+z$ with leftmost value $9/10.$ This concludes the proof.

Addendum, next day. We are not required to simplify the sum that appears in $w=0,$ but we may do so. We get $$S_n = \sum_{q=0}^{n-1} {q+n-1\choose n-1} 2^{n-q} = 2^n [z^{n-1}] \frac{1}{1-z} \frac{1}{(1-z/2)^n} \\ = (-1)^{n+1} 2^{2n} \mathrm{Res}_{z=0} \frac{1}{z^{n}} \frac{1}{z-1} \frac{1}{(z-2)^n}.$$ Residues sum to zero and the residue at infinity is zero by inspection. The residue at $z=1$ contributes $-2^{2n}.$ The residue at $z=2$ requires $$\frac{1}{(2+(z-2))^n} \frac{1}{1+(z-2)} = \frac{1}{2^n} \frac{1}{(1+(z-2)/2)^n} \frac{1}{1+(z-2)}.$$ and we get the contribution $$(-1)^{n+1} 2^n \sum_{q=0}^{n-1} {q+n-1\choose n-1} (-1)^q 2^{-q} (-1)^{n-1-q} = S_n.$$ This shows that $2 S_n - 2^{2n} = 0$ or $S_n = 2^{2n-1}.$