Recurrence formula for a series $x_n$ -- very stuck!!! The Problem:
$x_n$ is defined as $$\sum_{k=0}^\infty \frac{(n+k)!}{k!(2n+2k)!}(\frac{1}{2})^{2k} $$
and satisfies the recurrence: $x_n-2(2n+1)x_{n+1}=x_{n+2}$
But I cannot show that this is the case... 
My Attempt:
$$LHS=\sum_{k=0}^\infty\frac{(n+k)!}{k!(2n+2k)!}(\frac{1}{2})^{2k}-2(2n+1)\frac{(n+1+k)!}{k!(2n+2+2k)!}(\frac{1}{2})^{2k}$$
$$=\sum_{k=0}^\infty\frac{(n+k)!(2n+1+2k)(2n+2+2k)}{k!(2n+2+2k)!}(\frac{1}{2})^{2k}-2(2n+1)\frac{(n+1+k)!}{k!(2n+2+2k)!}(\frac{1}{2})^{2k}$$
$$=\sum_{k=0}^\infty\frac{2(n+k)!(n+1+k)(2n+1+2k)-2(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(\frac{1}{2})^{2k}$$
$$=\sum_{k=0}^\infty\frac{2(n+1+k)!( (2n+1+2k)-(2n+1))}{k!(2n+2+2k)!}(\frac{1}{2})^{2k}$$
$$=\sum_{k=0}^\infty\frac{2(n+1+k)!( 2k)}{k!(2n+2+2k)!}(\frac{1}{2})^{2k}$$
$$=\sum_{k=0}^\infty\frac{2(n+2+k)!( 2k)}{k!(2n+2+2k)!(n+2+k)}(\frac{1}{2})^{2k}$$
$$=\sum_{k=0}^\infty\frac{(n+2+k)!}{(k-1)!(2n+2+2k)!(2n+4+2k)}(\frac{1}{2})^{2(k-1)-1}$$
But from this point, I have no idea how to obtain $x_{n+2}$ from this...

We have that $\frac{1}{(2n+2k)!}$ is the coefficient of $z^{n+k}$ in $\sum_{m\geq 0}\frac{z^m}{(2m)!}=\cosh(\sqrt{z})$.
On the other hand, by stars and bars we have that $\frac{1}{4^k}\binom{n+k}{k}$ is the coefficient of $z^k$ in
$$ \sum_{m\geq 0}\binom{n+m}{m}\frac{z^m}{4^m}=\frac{1}{(1-z/4)^{n+1}} $$
or the coefficient of $z^{-k}$ in $\left(1-\frac{1}{4z}\right)^{-1-n}$, so that
$$ \sum_{k\geq 0}\frac{(n+k)!}{4^k k!(2n+2k)!} = n!\cdot[z^n]\frac{\cosh(\sqrt{z})}{\left(1-\frac{1}{4z}\right)^{n+1}}=n!\cdot [z^{2n}]\frac{\cosh z}{\left(1-\frac{1}{4z^2}\right)^{n+1}}. $$
By using Cauchy integral formula and the residue theorem, we may check that
$x_n$ is related with the Fourier series of $e^{-\cos\theta}$ over $(-\pi,\pi)$. In particular, we have:
$$ x_n = \sum_{k\geq 0}\frac{(n+k)!}{4^k k!(2n+2k)!} = \frac{\sqrt{\pi}}{2}\cdot I_{\frac{2n-1}{2}}\left(\frac{1}{2}\right) $$
where $I_\nu$ is a modified Bessel function of the first kind. The recurrence relation for the $x_n$ sequence then follows from the integral representation of such function, the cosine addition formulas and integration by parts, as exploited here. Notably, given such recurrence relation, we also have that $x_n$ is a linear combination of $\cosh\frac{1}{2}$ and $\sinh\frac{1}{2}$ for any $n\in\mathbb{N}$.
