special functions - Summation of factorial products

Can someone give me a hint on how to evaluate the following expression:

$$\sum_{r=0}^{n} \frac{(k-2r)!}{(n-r)!(2r)!}, \ \ \ \text{where }k > n$$

or equivalently (up to a multiplicative constant, not sure of the usefulness of this formulation):

$$\sum_{r=0}^{n} \binom{n}{r} \frac{(k-2r)!}{2^n(2r-1)!!}$$

I have been trying to evaluate it for a while but made no progress, so I would appreciate any help you can give me.

Answer

Let's start with a hypergeometric function and modify it so as to reach closer to your sum expression.

Hypergeometric function is defined for $|z|<1$ by the power series,

$\,_2F_1(a,b;c;z) = \sum\limits_{r=0}^{r=\infty}\frac{(a)_r (b)_r}{(c)_r} \frac{z^r}{r!}$

which is undefined if $c$ is nonpositive and $(q)_n$ is (rising) Pochhammer symbol.

So, first we will replace $c$ with a nonpositive number which probably should be $\frac{1}{2}$ as per your sum expression. Then, $(c)_r$ will become

$(\frac{1}{2})_r$
$= \frac{1}{2}(\frac{1}{2}+1)...(\frac{1}{2}+r-2)(\frac{1}{2}+r-1)$

$= \frac{1}{2^r} 1(2+1)...(2(r-2)+1)(2(r-1)+1)$

$= \frac{1}{2^r} 1(2+1)...(2r-3)(2r-1)$

$= \frac{1}{2^r} \frac{1(2)(2+1)...(2r-4)(2r-3)(2r-2)(2r-1)}{(2)(4)...(2r-4)(2r-2)}$

$= \frac{1}{2^r} \frac{(2r-1)!}{2^{r-1}\, (r-1)!}$

$= \frac{1}{2^r} \frac{(2r)!}{2^{r}\, r!}$

$= \frac{1}{2^{2r}} \frac{(2r)!}{r!}$

Replacing $(c)_r = (\frac{1}{2})_r$ in the power series we get,

$\,_2F_1(a,b;\frac{1}{2};z) = \sum\limits_{r=0}^{r=\infty}\frac{(a)_r (b)_r}{(2r)!} 2^{2r}z^r$

Now, let's replace $a$ by $-n$. Then, $(a)_r$ will become

$(-n)_r=(-n)(-n+1)...(-n+r-1)$

$=(-1)^r n(n-1)...(n-(r-1))$ (which becomes $0$ if $r>n$)

$=(-1)^r \frac{n!}{(n-r)!}$

Replacing $(c)_r = (\frac{1}{2})_r$ in the power series and changing limits appropriately, we get,

$\,_2F_1(-n,b;\frac{1}{2};z) = \sum\limits_{r=0}^{r=n}\frac{(-1)^r \, n! \, (b)_r}{(n-r)! (2r)!} 2^{2r}z^r = n! \, \sum\limits_{r=0}^{r=n}\frac{(b)_r}{(n-r)! (2r)!} 2^{2r}(-z)^r$

Now, I am stuck at this point. Will edit soon once solved.