How to closed the sum $\displaystyle \sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$

Question

How to closed the sum $\displaystyle S=\sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$

I'm trying divide two cases $n$ odd and $n$ even. I predict that

$S=\begin{cases}\dfrac{1}{2^n\left[\left(\frac{n}{2}\right)!\right]^2}, & \quad \text{if $n$ even} \\ \\ \dfrac{-1}{2^n\left(\frac{n-1}{2}\right)!\left(\frac{n+1}{2}\right)!}, & \quad \text{if $n$ odd}\end{cases}$

or I can write

$\displaystyle S=\sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}= \dfrac{(-1)^n\left(\frac{2n-1-(-1)^n}{2}\right)!!}{n!\left(\frac{2n+1-(-1)^n}{2}\right)!!}$

Now I want you to help me prove it.

Answer 1

Here's a way to get the sum by obtaining the required generating function.

As in my first answer, rewrite the sum as:

$ \displaystyle \sum_{0 \le k \le n} \dfrac{(-1)^k }{n!\, 2^k}\dbinom{2\,k+1}{k}\, \dbinom{n}{n-k}\tag 1 $ Let

$\displaystyle a_k=\dfrac{(-1)^k }{2^k}\dbinom{2\,k+1}{k} $

The generating function for $a_k$ is:

$\displaystyle g(x)=\dfrac{2}{\sqrt{1+2\,x}}-\dfrac{2}{1+\sqrt{1+2\,x}} \tag 2 $

Then, we make use of the Euler's transform (reference), which states:

If

$\displaystyle g(x)=\sum_{k\ge 0} a_k\, x^k $

then

$\displaystyle \frac{1}{1-x}\, g\left(\frac{x}{1-x}\right)=\sum_{n\ge 0}\left( \sum_{k=0}^n \binom{n}{k}\, a_k \right)\, x^n $

Hence, on transformation $(2)$ becomes:

$\displaystyle \begin{align} E(x)&=\frac{1}{1-x}\, g\left(\frac{x}{1-x}\right)\\ &=\frac{1}{x}\left(1-\frac{\sqrt{1-x^2}}{1+x}\right) \tag 3 \end{align} $

which is the required g.f. for $(1)$.

To extract the coefficient, we can use the binomial series expansion for $(1-x^2)^{1/2}$ and use the identity described here:

$\displaystyle \sum_{k=0}^n \; {\alpha\choose k} \; (-1)^k = {\alpha-1 \choose n} \;(-1)^n \tag 4 $

So,

$ \begin{align} (1-x^2)^{1/2} &= \sum_{n\ge 0} (-1)^n\, \dbinom{1/2}{n}\, x^{2\, n}\\ \frac{(1-x^2)^{1/2}}{1+x} &= \sum_{n\ge 0} \left(\sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k\, \dbinom{1/2}{k}\right)\, x^{n}\\ &= \sum_{n\ge 0} (-1)^{\lceil n/2 \rceil}\, \dbinom{-1/2}{\lfloor n/2\rfloor} x^n \tag {using eq. 4}\\ \implies E(x) &= \sum_{n\ge 0} (-1)^{\lfloor n/2 \rfloor}\, \dbinom{-1/2}{\lceil n/2\rceil} x^n \end{align} $ Therefore, the sum $(1)$ is:

$ \displaystyle \sum_{ k=0}^{n} \dfrac{(-1)^k }{n!\, 2^k}\dbinom{2\,k+1}{k}\, \dbinom{n}{n-k} = \boxed{\displaystyle \frac{(-1)^{\lfloor n/2 \rfloor}}{n!}\, \dbinom{-1/2}{\lceil n/2\rceil}} $

Answer 2

I'm assuming $(2 k + 1)!! = 1 \cdot 3 \cdot \ldots \cdot (2 k + 1) = \frac{(2 k + 1)!}{2^k k!}$, so that the sum is: $$ \sum_{0 \le k \le n} \frac{(-1)^k (2 k + 1)!}{2^k (n - k)! (k!)^2 (k + 1)!} $$ maxima's implementation of the Gosper-Zeilberger algorithm (see e.g. Petkovsek, Wilf, Zeilberger's "A = B") tells me this isn't Gosper-summable, so there is little hope for a closed form.

Answer 3

We can also rewrite the summation as:

$\displaystyle \sum_{0 \le k \le n} \frac{(-1)^k }{n!\, 2^k}\dbinom{2\,k+1}{k}\, \dbinom{n}{n-k}\tag 1 $

Next, consider the convolution of generating functions:

$$\displaystyle \left(\sum_{k\ge 0}\, a_k\, x^k\right)\left(\sum_{k\ge 0}\, b_k\, x^k\right)=\sum_{n\ge 0}\left(\sum_{k=0}^n\, a_k\, b_{n-k}\right)\, x^n $$

Take $a_k=\dfrac{(-1)^k }{\, 2^k}\dbinom{2\,k+1}{k}$ and $b_k=\dbinom{n}{k}$

and their corresponding g.fs are:

\begin{align} A(x) &= \dfrac{2}{\sqrt{1+2\,x}}-\dfrac{2}{1+\sqrt{1+2\,x}}\\ B(x) &= (1+x)^n \end{align}

and the sum $(1)$ is $\dfrac{[x^n]}{n!}$ in $A(x)\cdot B(x)$

It appears to be that

$$\displaystyle \sum_{ k=0}^{n} \frac{(-1)^k }{n!\, 2^k}\dbinom{2\,k+1}{k}\, \dbinom{n}{n-k}=\boxed{(-1)^n\, \dfrac{\displaystyle \binom{n}{\displaystyle\left\lfloor n/2\right\rfloor}}{2^n\, n!}} $$

Answer 4

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

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

Introduce $${2k+1\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2k+1}}{z^{k+1}} \; dz.$$

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

This is $$\frac{(-1)^n}{2^n} \left([z^n](1+z^2)^n + [z^{n-1}] (1+z^2)^n\right).$$

When $n$ is even the first term contributes and we obtain $$\frac{(-1)^n}{2^n} {n\choose n/2}.$$ When $n$ is odd the second term contributes and we obtain $$\frac{(-1)^n}{2^n} {n\choose (n-1)/2}.$$

Joining these two formulas we obtain $$\frac{(-1)^n}{2^n} {n\choose \lfloor n/2\rfloor}.$$