# How to prove $\sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m$?

Question: How to prove the following identity? $$\sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m.$$ I'm also looking for the generalization of this identity like $$\sum_{s=k}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=?$$

Proofs, hints, or references are all welcome.

• Could it be s-m instead of m-s? – cgo Dec 4 '15 at 11:39
• A related question. – Lucian Dec 12 '15 at 8:55

Let $$a_m=\sum_{s=0}^{m}\binom{2s}{s}\binom{s}{m-s}\dfrac{(-1)^s}{s+1}$$and let $P(x)=\displaystyle\sum_{m=0}^{\infty}a_m x^m$ be the generating function for $a_m$. We can rewrite $P(x)$ as $$\sum_{m=0}^{\infty}\sum_{s=0}^{m}\binom{2s}{s}\binom{s}{m-s}\frac{(-1)^s}{s+1}x^m=\sum_{s=0}^{\infty}\sum_{m=s}^{\infty}\binom{2s}{s}\binom{s}{m-s}\frac{(-1)^s}{s+1}x^m$$The second sum is really the same thing as a sum of $m-s$ from $0$ to $\infty$, so we can write it as so and take out the terms that don't involve $m$: $$\sum_{s=0}^{\infty}\binom{2s}{s}\frac{(-1)^s}{s+1}x^s\sum_{m-s=0}^{\infty}\binom{s}{m-s}x^{m-s}$$By the binomial theorem, the above is equal to $$\sum_{s=0}^{\infty}\binom{2s}{s}\frac{(-1)^s}{s+1}x^s (1+x)^s=\sum_{s=0}^{\infty}\binom{2s}{s}\frac{1}{s+1}(-x-x^2)^s$$From the generating function of the Catalan numbers, $\displaystyle\sum_{n=0}^{\infty}\binom{2n}{n}\dfrac{1}{n+1}x^n=\dfrac{1-\sqrt{1-4x}}{2x}$, this last expression is equal to $$\frac{1-\sqrt{1+4x+4x^2}}{-2x-2x^2}=\frac{-2x}{-2x-2x^2}=\frac{1}{x+1}=1-x+x^2-x^3+\cdots$$So to conclude, we know that $$\sum_{m=0}^{\infty}a_m x^m=\sum_{m=0}^{\infty}(-1)^m x^m\Leftrightarrow a_m=(-1)^m$$This method is known as the snake oil method. To evaluate the more general expression, you'll need to truncate some of the terms at the beginning of the sum.

• Nice solution! +1 – Markus Scheuer Dec 4 '15 at 21:37
• Very nice! Thanks! – Ji-Cai Liu Dec 5 '15 at 9:03

Suppose we seek to verify that

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

without using the generating function of the Catalan numbers.

Re-write the sum as follows: $$\sum_{s=0}^m {2s\choose m} {m\choose s} \frac{(-1)^s}{s+1}$$

which is $$\frac{1}{m+1} \sum_{s=0}^m {2s\choose m} {m+1\choose s+1} (-1)^s$$

which turns into $$- \frac{1}{m+1} \sum_{s=1}^{m+1} {2s-2\choose m} {m+1\choose s} (-1)^{s} \\ = \frac{1}{m+1} {-2\choose m} - \frac{1}{m+1} \sum_{s=0}^{m+1} {2s-2\choose m} {m+1\choose s} (-1)^{s} \\ = \frac{1}{m+1} (-1)^m \frac{(m+1)!}{m!} - \frac{1}{m+1} \sum_{s=0}^{m+1} {2s-2\choose m} {m+1\choose s} (-1)^{s} \\ = (-1)^m - \frac{1}{m+1} \sum_{s=0}^{m+1} {2s-2\choose m} {m+1\choose s} (-1)^{s}.$$

Now introduce $${2s-2\choose m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{2s-2} \; dz.$$

We get for the sum $$- \frac{1}{m+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1+z)^2} \sum_{s=0}^{m+1} {m+1\choose s} (-1)^{s} (1+z)^{2s} \; dz \\ = -\frac{1}{m+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1+z)^2} (1-(1+z)^2)^{m+1}\; dz \\ = \frac{(-1)^m}{m+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1+z)^2} (z^2+2z)^{m+1} \; dz \\ = \frac{(-1)^m}{m+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)^2} (z+2)^{m+1} \; dz = 0.$$

This concludes the argument.

This is just a supplement to the nice answer of @tc2718. We show that it is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series. We can write e.g. $$\binom{n}{k}=[x^k](1+x)^n$$

We obtain \begin{align*} \sum_{s=0}^{m}&{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}\\ &= \sum_{s=0}^{m}[u^{m-s}](1+u)^s(-1)^s[x^s]\frac{1-\sqrt{1-4x}}{2x}\tag{1}\\ &= [u^{m}]\sum_{s=0}^{m}(1+u)^s(-u)^s[x^s]\frac{1-\sqrt{1-4x}}{2x}\tag{2}\\ &= [u^{m}]\frac{1-\sqrt{1-4(1+u)(-u)}}{2(1+u)(-u)}\tag{3}\\ &= [u^{m}]\frac{1-(1+2u)}{2(1+u)(-u)}\\ &= [u^{m}]\frac{1}{1+u}\\ &= [u^{m}]\sum_{s=0}^{\infty}(-u)^s\\ &=(-1)^m \end{align*}

Comment:

• In (1) we use the coefficient of operator together with the series expansion of the Catalan-numbers: $\frac{1-\sqrt{1-4x}}{2x}=\sum_{s=0}^{\infty}\frac{1}{s+1}\binom{2s}{s}x^s$

• In (2) we use the rule $[x^s]f(x)=[x^0]x^{-s}f(x)$

• In (3) we use the substitution rule $f(x):=\sum_{s=0}^{\infty}a_sx^s=\sum_{s=0}^\infty[y^s]f(y)x^s$

• (+1). Nice work. On line two you use what I like to call an annihilated coefficient extractor as presented at this MSE link I and this MSE link II. I believe you should mention that you can extend $s$ to infinity on line two because you are extracting the cofficient on $[u^m]$ and the terms with $s\gt m$ do not contribute, being multiples of $u^s.$ – Marko Riedel Dec 4 '15 at 23:42
• In theory when you compute the square root you need to justify your choice of branch and branch cut, but this feature only gains prominence when working with contour integrals. The principal branch of the logarithm with the cut on the negative real axis and argument from $-\pi$ to $\pi$ will produce the correct positive square root I believe. – Marko Riedel Dec 4 '15 at 23:57
• @MarkoRiedel: Annihilent coefficient extractor is a nice term. I think I've read about something similar in one of Apostols book in the conext of operators and diff equations. I became acquainted with the technique I've used above when learning about algorithms from Knuth. +1 – Markus Scheuer Dec 5 '15 at 7:09
• @MarkiRiedel: Regarding your second comment, I'm of course aware of it, but I think in case assuming that the series representation of Catalan Numbers is known then we had already done these considerations before that, otherwise we couldn't use the series representation. And these considerations are essential in any case! :-) – Markus Scheuer Dec 5 '15 at 7:29