Prove that $\sum_{k=0}^{2n} \binom {2n+k}{k} \binom{2n}{k} \frac{(-1)^k}{2^k} \frac{1}{k+1} = 0. $

Question

Let $n$ be a positive integer. Prove that $$ \sum_{k=0}^{2n} \binom {2n+k}{k} \binom{2n}{k} \frac{(-1)^k}{2^k} \frac{1}{k+1} = 0. $$

I am trying to solve this by using induction on $n$. I have proven the sum to be zero in the case $n=1$. Assuming that the sum is zero for $n=m$ ($m$ is a positive integer), how do I prove that it implies that the sum is zero for $n=m+1$?

Can I get some hints?

Answer 1

Let's approach the sum through the Hypergeometric Function.
To this purpose let's rewrite it as $$ \eqalign{ & S(n) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,2n} \right)} {\binom{2n+k}{k} \binom{2n}{k} {{\left( { - 1} \right)^{\,k} } \over {2^{\,k} \left( {k + 1} \right)}}} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,2n} \right)} {\binom{2n+k}{k} \binom{2n}{k} {1 \over {\left( {k + 1} \right)}}\left( { - {1 \over 2}} \right)^{\,k} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,2n} \right)} {t_{\,k} \left( { - {1 \over 2}} \right)^{\,k} } \cr} $$

The $t_k$ are in the following ratio $$ \eqalign{ & t_{\,0} = 1 \cr & {{t_{\,k + 1} } \over {t_{\,k} }} = \cr & = {{\left( {2n + k + 1} \right)!} \over {\left( {k + 1} \right)!\left( {k + 1} \right)!\left( {2n - k - 1} \right)!\left( {k + 2} \right)}} {{k!k!\left( {2n - k} \right)!\left( {k + 1} \right)} \over {\left( {2n + k} \right)!}} = \cr & = - {{\left( {k + 2n + 1} \right)\left( {k - 2n} \right)} \over {\left( {k + 2} \right)}}{1 \over {\left( {k + 1} \right)}} \cr} $$ so the sum can be expressed as $$ \eqalign{ & S(n) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,2n} \right)} {\binom{2n+k}{k} \binom{2n}{k} {{\left( { - 1} \right)^{\,k} } \over {2^{\,k} \left( {k + 1} \right)}}} = \cr & = {}_2F_{\,1} \left( {\left. {\matrix{ {2n + 1,\; - 2n} \cr 2 \cr } \,} \right|1/2} \right) \cr} $$

For $n=0$ this gives $$ S(0) = {}_2F_{\,1} \left( {\left. {\matrix{ {1,\;0} \cr 2 \cr } \,} \right|1/2} \right) = 1 $$ while for $0<n$ we have $$ \eqalign{ & {}_2F_{\,1} \left( {\left. {\matrix{ {2n + 1,\; - 2n} \cr 2 \cr } \,} \right|1/2} \right)\quad \left| {\;0 < n} \right.\quad = \cr & = {{\Gamma \left( 2 \right)} \over {\Gamma \left( {2n + 1} \right)\Gamma \left( { - 2n} \right)}}\sum\limits_{0\, \le \,k\,} {{{\Gamma \left( {2n + 1 + k} \right)\Gamma \left( { - 2n + k} \right)} \over {\Gamma \left( {2 + k} \right)}}} {1 \over {2^{\,k} k!}} \cr} $$

Note that we can arrive to the same result by expressing the binomials through the Gamma function and performing some algebraic simplifications.

To the fraction outside the sum we can apply the Reflection formula for the Gamma function, which in the inverted form is valid all over the complex field $$ {1 \over {\Gamma \left( {z + 1} \right)\,\Gamma \left( { - z} \right)}} = - {{\sin \left( {\pi \,z} \right)} \over \pi }\quad \left| {\;\forall z \in \mathbb C} \right. $$ then clearly $$ S(n)\quad \left| {\;0 < n \in Z} \right. = \sin \left( {2\pi \,n} \right) \cdot \left( \cdots \right) = 0 $$

Answer 2

Starting from

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

we get

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

The last step is zero by inspection since we are extracting a coefficient on an odd power from a polynomial where all the powers are even, and we have the claim.

Answer 3

I prefer Marko Riedels result, since it doesn‘t require prerequisites, but for the record:

$$ \sum\limits_{ {0 \le } k { \le 2n} } {\binom{2n+k}{2n} \binom{2n}{k} {{\left( \frac{ - t}{2} \right)^{k} }}} = P_{2n}(1-t) $$ with the Legendre Polynomial $P_{2n}$. It is not too difficult to show, by using the recurrence for the Legendre polynomials $P_n(x)$ i.e. $$ 0 = (n+1) P_{n+1}(x) - (2n+1)xP_n(x) + nP_{n-1}(x) \, . $$ Plugging in the above expression for $n$ instead of $2n$ yields \begin{align} \sum_{k=0}^{n+1} \left(\frac{-t}{2}\right)^k \Bigg\{ &(n+1) \binom{n+1+k}{n+1} \binom{n+1}{k} - 2(2n+1) \binom{n+k-1}{n} \binom{n}{k-1} \\ &-(2n+1) \binom{n+k}{n} \binom{n}{k} + n \binom{n-1+k}{n-1} \binom{n-1}{k} \Bigg\} = 0 \end{align} which vanishes termwise after some lengthy but not difficult algebra after converting to factorials; here $\binom{n}{k}=0$ if $k>n$. Then $$ \int_0^1 P_{2n}(1-t) \, {\rm d}t = \int_0^1 P_{2n}(t) \, {\rm d}t = \frac{1}{2^{2n}(2n)!} \frac{{\rm d}^{2n-1}}{{\rm d}t^{2n-1}} \left( t^2 -1\right)^{2n} \Bigg|_{t=0}^{t=1} = 0 $$ by Rodrigues formula and the fact that an odd number of derivatives always leaves at least a single $t$ in each term and since $2n-1 < 2n$ each term will also contain a factor $(t^2-1)$.

Answer 4

Residue Approach $$ \begin{align} \sum_{k=0}^{2n}\binom{2n+k}{k}\binom{2n}{k}\frac{(-1)^k}{2^k}\frac1{k+1} &=\frac1{2n+1}\sum_{k=0}^{2n}\binom{-2n-1}{k}\binom{2n+1}{k+1}\frac1{2^k}\\ &=\frac1{2n+1}\sum_{k=0}^{2n}\binom{-2n-1}{k}\binom{2n+1}{2n-k}\frac1{2^k}\\ &=\frac1{2n+1}\left[x^{2n}\right]\left(1+\frac x2\right)^{-2n-1}(1+x)^{2n+1}\\ &=\frac1{2n+1}\left[x^{-1}\right]\left(\frac1{x+2}+\frac1x\right)^{2n+1}\tag1 \end{align} $$ So, we are interested in the residue at $x=0$ of $$ f(x)=\left(\frac1{x+2}+\frac1x\right)^{2n+1}\tag2 $$ which is the same as the residue at $x=0$ of $$ -f(-x)=\left(\frac1{x-2}+\frac1x\right)^{2n+1}\tag3 $$ Since $-f(-x)=f(x-2)$, this is the residue of $f(x)$ at $x=-2$.

Thus, the residues of $f(x)$ at $x=0$ and $x=-2$ are equal.

For $|x|\gt2$, $|f(x)|\le\left(\frac2{|x|-2}\right)^{2n+1}$, and for $n\ge1$, $$ \left|\int_{|x|=R}f(x)\,\mathrm{d}x\right|\le2\pi R\left(\frac2{R-2}\right)^{2n+1}\stackrel{R\to\infty}{\longrightarrow}0\tag4 $$ Thus, Cauchy's Residue Theorem says the sum of the residues is $0$. Therefore, for $n\ge1$, we get that both residues are $0$.

This means that for $n\ge1$, $$ \sum_{k=0}^{2n}\binom{2n+k}{k}\binom{2n}{k}\frac{(-1)^k}{2^k}\frac1{k+1}=0\tag5 $$

---

A More Elementary Approach $$ \begin{align} &\sum_{k=0}^{2n}\binom{2n+k}{k}\binom{2n}{k}\frac{(-1)^k}{2^k}\frac1{k+1}\\ &=\frac1{2n+1}\sum_{k=0}^{2n}\binom{2n+k}{2n}\binom{2n+1}{k+1}\left(-\frac12\right)^k\tag6\\ &=\frac1{2n+1}\sum_{k=0}^{2n}\left[x^{2n}\right](1+x)^{2n+k}\binom{2n+1}{k+1}\left(-\frac12\right)^k\tag7\\ &=\frac1{2n+1}\left[x^{2n}\right](1+x)^{2n}\sum_{k=0}^{2n}\binom{2n+1}{k+1}\left(-\frac{1+x}2\right)^k\tag8\\ &=-\frac2{2n+1}\left[x^{2n}\right](1+x)^{2n-1}\sum_{k=0}^{2n}\binom{2n+1}{k+1}\left(-\frac{1+x}2\right)^{k+1}\tag9\\ &=-\frac2{2n+1}\left[x^{2n}\right](1+x)^{2n-1}\left[\left(\frac{1-x}2\right)^{2n+1}-1\right]\tag{10}\\ &=-\frac2{2n+1}\left[x^{2n}\right]\left[\left(\frac{1-x^2}2\right)^{2n-1}\left(\frac{1-x}2\right)^2-(1+x)^{2n-1}\right]\tag{11}\\ &=-\frac2{2n+1}\left[x^{2n}\right]\left[\left(\frac{1-x^2}2\right)^{2n-1}\frac{1+x^2}4\right]\tag{12}\\ &=-\frac{2^{-2n}}{2n+1}\left(\left[x^{2n}\right]\left(1-x^2\right)^{2n-1}+\left[x^{2n-2}\right]\left(1-x^2\right)^{2n-1}\right)\tag{13}\\[6pt] &=-\frac{2^{-2n}}{2n+1}\left((-1)^n\binom{2n-1}{n}+(-1)^{n-1}\binom{2n-1}{n-1}\right)\tag{14}\\[12pt] &=0\tag{15} \end{align} $$ Explanation:
$\phantom{1}(6)$: $\binom{2n+k}{k}=\binom{2n+k}{2n}$ and $\frac1{k+1}\binom{2n}{k}=\frac1{2n+1}\binom{2n+1}{k+1}$
$\phantom{1}(7)$: $\binom{2n+k}{2n}=\left[x^{2n}\right](1+x)^{2n+k}$
$\phantom{1}(8)$: move $(1+x)^k$ inside the sum
$\phantom{1}(9)$: move $-\frac2{1+x}$ outside the sum
$(10)$: Binomial Theorem
$(11)$: distribute $(1+x)^{2n-1}$
$(12)$: toss out odd powers and powers too small (if $n\ge1$)
$(13)$: $\left[x^{2n}\right]x^2f(x)=\left[x^{2n-2}\right]f(x)$
$(14)$: Binomial Theorem
$(15)$: evaluate

Answer 5

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[10px,#ffd]{% \left.\sum_{k\ =\ 0}^{2n}{2n + k \choose k}{2n \choose k} {\pars{-1}^{k} \over 2^{k}}{1 \over k + 1} \,\right\vert_{\large\ n\ \in\ \mathbb{N}_{\ >\ 0}}} \\[5mm] = &\ -2\sum_{k\ =\ 0}^{2n} {2n \choose k}\braces{\bracks{z^{k}}\pars{1 + z}^{2n + k}} \int_{0}^{-1/2}t^{k}\,\dd t \\[5mm] = &\ 2\bracks{z^{0}}\pars{1 + z}^{2n}\int_{-1/2}^{0}\sum_{k\ =\ 0}^{2n} {2n \choose k}\bracks{\pars{1 + z}t \over z}^{k}\,\dd t \\[5mm] = &\ 2\bracks{z^{0}}\pars{1 + z}^{2n}\int_{-1/2}^{0} \bracks{1 + {\pars{1 + z}t \over z}}^{2n}\,\dd t \\[5mm] = &\ {1 \over 2n +1}\bracks{z^{2n}}\pars{1 + z}^{2n - 1} \bracks{2^{-2n}\pars{1 - z}^{2n + 1} + 2z^{2n + 1}} \\[5mm] = &\ {1 \over 2^{2n}\pars{2n +1}}\bracks{z^{2n}} \pars{1 + z}^{2n - 1}\pars{1 - z}^{2n + 1} \\[5mm] = &\ {1 \over 2^{2n}\pars{2n - 1}}\bracks{z^{2n}} \pars{1 - z^{2}}^{2n -1}\pars{1 - 2z + z^{2}} \\[5mm] = &\ {1 \over 2^{2n}\pars{2n +1}} \times \\[2mm] &\ \!\!\!\!\!\braces{\bracks{z^{2n}}\pars{1 - z^{2}}^{2n - 1} - 2\bracks{z^{2n - 1}}\pars{1 - z^{2}}^{2n - 1} + \bracks{z^{2n - 2}}\pars{1 - z^{2}}^{2n - 1}} \\[5mm] = &\ {1 \over 2^{2n}\pars{2n +1}} \bracks{{2n - 1 \choose n}\pars{-1}^{n} + \underbrace{{2n - 1 \choose n - 1}}_{\ds{=\ {2n - 1 \choose n}}} \pars{-1}^{n - 1}} = \bbx{\large 0} \\ & \end{align}