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?

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.