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.
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.