Evaluating $\sum_{k=0}^n \frac{1}{(2k+1)!(2(n-k))!}$ Evidently:
$$\sum_{k=0}^n \frac{1}{(2k+1)!(2(n-k))!} = \frac{4^n}{(2n+1)!}$$
(says wolfram alpha)
But what is a good way to come up with this?
 A: Multiplying by $(2n+1)!\over (2n+1)!$ might help, as this is the result of adding $2k+1$ to $2(n-k)$.
$$\frac 1{(2n+1)!}\sum_{k=0}^n\frac{(2n+1)!}{(2k+1)!(2(n-k))!}=\frac 1{(2n+1)!}\sum_{k=0}^{2n+1}{2n+1\choose k}-\frac 1{(2n+1)!}\sum_{k=0}^{n}{2n+1\choose 2k}\\
=\frac 12\frac 1{(2n+1)!}\sum_{k=0}^{2n+1}{2n+1\choose k}=\frac{2^{2n+1}}{2(2n+1)!}$$
I expect you can take it from here.
Note that
$$\sum_{k=0}^{2n+1}(-1)^k{2n+1\choose k}=0$$
which is where the result
$$\sum_{k=0}^{2n+1}{2n+1\choose k}-\sum_{k=0}^{n}{2n+1\choose 2k}=\frac 12\sum_{k=0}^{2n+1}{2n+1\choose k}$$
arises from.
A: By the binomial theorem,
$$(1+1)^{2n+1}-(1-1)^{2n+1}=\sum_{i=0}^{2n+1}(1-(-1)^i)\binom{2n+1}i=2\sum_{i=0,\text{odd }i}^n\binom{2n+1}{i}\\=2\sum_{k=0}^n\binom{2n+1}{2k+1},$$
because the terms with even $i$ cancel out.
Hence using the factorial representation of the binomial coefficients,
$$2^{2n+1}-0^{2n+1}=2\sum_{k=0}^n\frac{(2n+1)!}{(2k+1)!(2n+1-2k-1)!},$$
$$\frac{4^n}{(2n+1)!}=\sum_{k=0}^n\frac1{(2k+1)!(2(n-k))!}.$$
