Proving $\sum\limits_{k=0}^{n-1}\frac{\left(-1\right)^{n-k-1}\binom{2n}{2k+1}\binom{2k}{k}\binom{2n-2k}{n-k}}{2^{2n}\binom{n}{k}} = (-1)^{n-1}$

Question

I found the below combinatorial identity seems true:

$$\sum\limits_{k=0}^{n-1}\frac{\left(-1\right)^{n-k-1}\binom{2n}{2k+1}\binom{2k}{k}\binom{2n-2k}{n-k}}{2^{2n}\binom{n}{k}} = (-1)^{n-1}$$

but I have no idea how to prove it, anyone has some ideas?

Here is where this problem comes from.

I want to prove this Fourier series expansion

$\log\left(2\cos\frac{\theta}{2}\right)=\sum_{n=1}^{\infty}\frac{\left(-1\right)^{n-1}\cos n\theta}{n}$

then I try to calculate the coefficients by evaluating the following integral

\begin{eqnarray} a_{n}&=&\frac{2}{\pi}\int_{0}^{\pi}\cos\left(n\theta\right)\log\left(2\cos\frac{\theta}{2}\right)d\theta\\&=&\frac{2}{n\pi}\int_{0}^{\pi}\frac{\sin\left(n\theta\right)\sin\frac{\theta}{2}}{2\cos\frac{\theta}{2}}d\theta\\&=&\frac{\left(-1\right)^{n-1}}{n}\\A_{n}&=&\int_{0}^{\pi}\sin\left(n\theta\right)\tan\frac{\theta}{2}d\theta\\&=&2\int_{0}^{\frac{\pi}{2}}\sin\left(2n\theta\right)\tan\theta d\theta\\&=&2\sum_{k=0}^{n-1}\left(-1\right)^{n-k-1}\left(\begin{array}{c} 2n\\ 2k+1 \end{array}\right)\int_{0}^{\frac{\pi}{2}}\left(\cos\theta\right)^{2k}\left(\sin\theta\right)^{2n-2k}d\theta\\&=&\sum_{k=0}^{n-1}\left(-1\right)^{n-k-1}\left(\begin{array}{c} 2n\\ 2k+1 \end{array}\right)\frac{\Gamma\left(\frac{2k+1}{2}\right)\Gamma\left(\frac{2n-2k+1}{2}\right)}{\Gamma(n+1)}\\&=&\pi\sum_{k=0}^{n-1}\left(-1\right)^{n-k-1}\left(\begin{array}{c} 2n\\ 2k+1 \end{array}\right)\frac{\left(\begin{array}{c} 2k\\ k \end{array}\right)k!\left(\begin{array}{c} 2n-2k\\ n-k \end{array}\right)(n-k)!}{2^{2n}n!}\\&=&\pi\sum_{k=0}^{n-1}\frac{\left(-1\right)^{n-k-1}\left(\begin{array}{c} 2n\\ 2k+1 \end{array}\right)\left(\begin{array}{c} 2k\\ k \end{array}\right)\left(\begin{array}{c} 2n-2k\\ n-k \end{array}\right)}{2^{2n}\left(\begin{array}{c} n\\ k \end{array}\right)}\\&=&2\pi\left(-1\right)^{n-1}? \end{eqnarray}

therefore, I have two questions:

(1) is there a direct way to evaluate the integral $A_n$ ?

(2) how to prove the identity in a combinatoric way ?

Answer 1

The claim is equivalent to $$\sum\limits_{k=0}^{n-1}\frac{\left(-1\right)^{k}\binom{2n}{2k+1}\binom{2k}{k}\binom{2n-2k}{n-k}}{4^n\binom{n}{k}} = 1$$

Brute force on this seems to work, but I don't have a very neat proof. The only non-standard identity we need (non-standard to me, anyway) is

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

To prove this, note that $$\left(1-x^2\right)^{n-1}=\sum_{k=0}^{n-1} \binom{n-1}{k}(-1)^k x^{2k}$$

so that $$\int_0^1 \left(1-x^2\right)^{n-1} dx =\sum_{k=0}^{n-1} \frac{(-1)^k}{2k+1} \binom{n-1}{k}$$

Substituting $x=\sin{u}$, this integral becomes $$\int_0^\frac{\pi}{2} \cos^{2n-1}{(u)} du =:I(2n-1)$$

and it's a standard result using integration by parts that $$I(N)=\frac{N-1}{N} I(N-2)$$ where $I(0)=\frac{\pi}{2}$ and $I(1)=1$.

The form we need is that $$I(2n-1) = \frac{2n-2}{2n-1} I(2n-3)$$

and it's easy to check by induction that this is indeed $$I(2n-1)=\frac{4^n}{2n\binom{2n}{n}}$$

---

With this, the rest is just manipulating binomial coefficients.

$$\begin{align} \sum\limits_{k=0}^{n-1}\frac{\left(-1\right)^{k}\binom{2n}{2k+1}\binom{2k}{k}\binom{2n-2k}{n-k}}{4^n\binom{n}{k}} &= \sum\limits_{k=0}^{n-1}\frac{\left(-1\right)^{k}(2n)! (2k)! (2n-2k)! k!(n-k)! }{4^n n! (2k+1)!(2n-2k-1)!k!^2 (n-k)!^2} \\ &= \sum\limits_{k=0}^{n-1}\frac{2\left(-1\right)^{k}(2n)! }{4^n n! (2k+1) k! (n-k-1)!} \\ &= \sum\limits_{k=0}^{n-1} \frac{2(2n)!}{4^n n!} \frac{(-1)^k}{(2k+1) k! (n-k-1)!} \\ &= \sum\limits_{k=0}^{n-1} \frac{2n(2n)!}{4^n (n!)^2} \frac{(-1)^k (n-1)!}{(2k+1) k! (n-k-1)!} \\ &= \frac{2n}{4^n}\binom{2n}{n} \sum\limits_{k=0}^{n-1}\frac{(-1)^k}{2k+1}\binom{n-1}{k} \\ &=1 \end{align}$$

by the result above, so the claim is proved.

Answer 2

Now that this question is no longer closed, I can post my previous comment as an answer.

Note that $$ \frac{\binom{2n}{2k+1}\binom{2k}{k}\binom{2n-2k}{n-k}}{2^{2n}\binom{n}{k}}=\frac{2n-2k}{2k+1}\binom{n}{k}\binom{2n}{n}. $$ This holds for $k=n$ as well, we just get $0=0$. Canceling $(−1)^{n-1}$ on both sides and clearing constants in $k$, we see that we only need to prove that $$ \sum_{k=0}^{n}(-1)^k\frac{2n-2k}{2k+1}\binom{n}{k}=\frac{2^{2n}}{\binom{2n}{n}}. $$ Now $n\ge 1$, so $\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0$. Adding that to the previous equation, we obtain $$ \sum_{k=0}^{n}(-1)^k\frac{2n+1}{2k+1}\binom{n}{k}=\frac{2^{2n}}{\binom{2n}{n}}, $$ i.e. $$ \sum_{k=0}^{n}(-1)^k\frac{1}{2k+1}\binom{n}{k}=\frac{2^{2n}}{(2n+1)\binom{2n}{n}}=\frac{(2n)!!}{(2n+1)!!}. $$ This formula has been proven and re-proven here many times, just use Approach0 to search for it. The basic idea of one of the solutions is that $$ \sum_{k=0}^{n}(-1)^k\frac{1}{2k+1}\binom{n}{k} =\int_{0}^{1}\sum_{k=0}^{n}\binom{n}{k}(-1)^kx^{2k}\,dx =\int_{0}^{1}\left(1-x^2\right)^n\,dx, $$ and integration by parts yields, for $n\ge 1$, $$ \begin{split} I_n&=\int_{0}^{1}\left(1-x^2\right)^n\,dx=\left[x\left(1-x^2\right)^n\right]_{0}^{1}-\int_{0}^{1}x(-2x)n\left(1-x^2\right)^{n-1}\,dx\\ &=2n\int_{0}^{1} x^2\left(1-x^2\right)^{n-1}\,dx=2n(I_n-I_{n-1}), \end{split} $$ so $$ I_n=\frac{2n}{2n+1}I_{n-1}, \qquad n\ge 1, $$ and $I_0=1$, which is easy to see.