How to closed the sum $\displaystyle \sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$ 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. 
 A: 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}}
$
A: 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.
A: 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!}}
$$
A: 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}.$$
