<s>[INST] 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?
 [/INST] 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)!!}.$$
</s>