How to apply induction to this formula? I want to justificate following equation:
$$\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!}\frac{1}{2k+1} = \frac{2^n}{(2n+1)!!}$$
I calculated the both sides for $n$ from 1 to 10 and it was true. How the mathematical induction can be applied to this equation? Or is there other way to justificate it?
 A: Do you strictly need to use induction? You may simply notice that
$$ \sum_{k=0}^{n}\frac{(-1)^k}{k!(n-k)!}\cdot\frac{1}{2k+1}=\frac{1}{n!}\int_{0}^{1}\sum_{k=0}^{n}\binom{n}{k}(-x^2)^k\,dx=\frac{1}{n!}\int_{0}^{1}(1-x^2)^n\,dx $$
and recall that $\int_{0}^{\pi/2}\left(\sin\theta\right)^{2n+1}\,d\theta = \frac{4^n}{(2n+1)\binom{2n}{n}}$ holds by integration by parts.
A: There is a standard technique for  this type of sum which has appeared
here several times. Introduce
$$f(z) = (-1)^n \frac{1}{2z+1} \prod_{q=0}^n \frac{1}{z-q}.$$
We use the fact that residues sum to zero and we have for the sum over
$0\le k\le n$
$$\sum_{k=0}^n \mathrm{Res}_{z=k} f(z)
= \sum_{k=0}^n (-1)^n \frac{1}{2k+1}
\prod_{q=0}^{k-1} \frac{1}{k-q}
\prod_{q=k+1}^{n} \frac{1}{k-q}
\\ = \sum_{k=0}^n (-1)^n \frac{1}{2k+1}
\frac{1}{k!} \frac{(-1)^{n-k}}{(n-k)!}
= \sum_{k=0}^n  
\frac{1}{k!} \frac{(-1)^k}{(n-k)!}
\frac{1}{2k+1}$$
so  this is  the target  sum. The  residue at  infinity is  zero since
$\lim_{R\to\infty}  2\pi R/R/R^{n+1}  = 0$  so  the sum  is minus  the
residue at $z=-1/2.$ We find
$$- \mathrm{Res}_{z=-1/2} f(z)
= \frac{(-1)^{n+1}}{2} \prod_{q=0}^n \frac{1}{-1/2-q}
= \frac{1}{2} \prod_{q=0}^n \frac{1}{1/2+q}
\\ =  2^n \prod_{q=0}^n \frac{1}{2q+1}
= \frac{2^n}{(2n+1)!!}.$$
A: You asked how to do this using induction.  To begin with, let's multiply everything by $n!$ so that we can express the terms using binomial coefficients: you want to show
$$ \sum_{k=0}^n (-1)^k \binom n k \frac{1}{2k+1} = \frac{(2n) ! ! }{(2n+1)!!}. $$
The difficulty you have is in making the inductive step go through: if you apply the Pascal's triangle identity for $\binom {n+1} k$ then you will end up with terms equivalent to $\binom n k \frac{1}{2k+3}$, and your inductive hypothesis is no help with these.  
This suggests strengthening the inductive hypothesis.  The right thing to try is proving by induction on $n$ that for any $r$, 
$$ \sum_{k=0}^n (-1)^k \binom n k \frac{1}{2k+ 2r+1} = (2r-1)!! \frac{(2n)!!}{(2n+2r+1)!!}$$ where you interpret $(2r-1)!!$ as 1 for $r=0$.  This is OK for $n=0$ and any $r$ (both sides are $1/(2r+1)$), and you can get the inductive step to go through by using the Pascal's triangle identity
$$ \binom {n+1} k = \binom n k + \binom n {k-1}.$$
A: The presence of the factor $1/(2k+1)$ in the summation implies that it can actually be obtained by integrating
$$\sum_{k=0}^n\frac{1}{k!(n-k)!}x^{2k},\tag{1}$$
with respect to $x$. Using the Binomial theorem (1) can be easily shown to have the closed form
$$\sum_{k=0}^n\frac{1}{k!(n-k)!}x^{2k}=\frac{(1+x^2)^n}{n!}.$$
Integrating both sides with respect to $x$,
$$\sum_{k=0}^n\frac{1}{k!(n-k)!}\frac{x^{2k+1}}{2k+1}=\frac{x \, _2F_1\left(\frac{1}{2},-n;\frac{3}{2};-x^2\right)}{n!},$$
where $_2F_1$ is the Hypergeometric function. Now let $x=i$ to obtain
$$\sum_{k=0}^n\frac{1}{k!(n-k)!}\frac{(-1)^k}{2k+1}=\frac{\, _2F_1\left(\frac{1}{2},-n;\frac{3}{2};1\right)}{n!}=\frac{\sqrt{\pi }}{2 \Gamma \left(n+\frac{3}{2}\right)}.$$
But $$\Gamma(m+1/2)=\frac{(2m-1)!!}{2^m}\sqrt{\pi},$$ so with $m=n+1$ we obtain the result
$$\sum_{k=0}^n\frac{1}{k!(n-k)!}\frac{(-1)^k}{2k+1}=\frac{\sqrt{\pi }}{2 \frac{(2(n+1)-1)!!}{2^{n+1}}\sqrt{\pi}}=\frac{2^n}{(2n+1)!!},$$ as required.
