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...
 A: 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}$.
A: $\displaystyle x_n=\sum\limits_{k=0}^\infty \frac{(n+k)!}{k!}\frac{(1/2)^{2k}}{(2n+2k)!}$
$\displaystyle =\sum\limits_{k=0}^\infty \frac{(n+k-1)!}{k!}\frac{(1/2)^{2k+1}}{(2n+2k-1)!}$
$\displaystyle = \sum\limits_{k=0}^\infty \frac{(n+k-1)!}{k!}\frac{(1/2)^{2k+1}}{(2n+2k-2)!} - \sum\limits_{k=0}^\infty \frac{(n+k)!(n+k-1)}{k!}\frac{(1/2)^{2k-1}}{(2n+2k)!} $
$\displaystyle = \sum\limits_{k=0}^\infty \frac{(n+k-1)!}{k!}\frac{(1/2)^{2k+1}}{(2n+2k-2)!} – (n-1)\sum\limits_{k=0}^\infty \frac{(n+k)!}{k!}\frac{(1/2)^{2k-1}}{(2n+2k)!} -\sum\limits_{k=0}^\infty \frac{(n+k+1)!}{k!}\frac{(1/2)^{2k+1}}{(2n+2k+2)!} $
$\displaystyle = \frac{1}{2}x_{n-1}-2(n-1)x_n- \frac{1}{2}x_{n+1}$
$n\to n+1$ => $x_{n+1}= \frac{1}{2}x_n-2n x_{n+1}- \frac{1}{2}x_{n+2}$ 
=>   $\enspace x_n-2(2n+1)x_{n+1}=x_{n+2}$
A: My Solution:
To verify that the recurrence is true: we simply test the LHS and the RHS $\Rightarrow$
$$LHS=x_n - 2(2n+1)x_{n+1}$$
$$=\sum_{k=0}^\infty \frac{2(n+k+1)!( (2n+2k+1)-(2n+1) )}{k!(2n+2+2k)!}\times(1/2)^{2k}$$
Note that this is equal to $0$ when $k=0$ so we may just consider the sum starting at $k=1$
$$=\sum_{k=1}^\infty\frac{(n+k+1)!}{(k-1)!( 2(n+2)+2(k-1))!}\times(1/2)^{2(k-1)}$$
$$=\sum_{k=1}^\infty\frac{((n+2)+(k-1))!}{(k-1)!( 2(n+2)+2(k-1))!}\times(1/2)^{2(k-1)}$$
$$=\sum_{k=0}^\infty\frac{((n+2)+(k))!}{(k)!( 2(n+2)+2(k))!}\times(1/2)^{2(k)}$$
$$=x_{n+2} \text{ as required}$$
