What is the order of magnitude of $\sum\limits_{n=1}^kn\binom{k}{n}\frac{(2k-2n-1)!!}{(2k-1)!!}$ as $k\to\infty$? What is the order of magnitude of the function $f(k)$ below in the limit as $k \rightarrow \infty$? Does it diverge, converge to a positive limit, or converge to zero?
$$
f(k) = \sum\limits_{n=1}^{k} n \binom{k}{n} \frac{(2k - 2n - 1)!! }{(2k-1)!! }
$$
Here $!!$ represents the double factorial. Does anyone have an hint?
 A: We can write your $f(k)$ in the form
$$
\sum\limits_{n = 1}^k {\frac{1}{{2^n (n - 1)!}}\frac{{\Gamma (k + 1)\Gamma \!\left( {k - n + \frac{1}{2}} \right)}}{{\Gamma \!\left( {k + \frac{1}{2}} \right)\Gamma (k - n + 1)}}} .
$$
Suppose that $k$ is large and fixed and consider
$$\tag{$*$}
\frac{1}{{(n - 1)!}}\frac{{\Gamma (k + 1)\Gamma \!\left( {k - n + \frac{1}{2}} \right)}}{{\Gamma \!\left( {k + \frac{1}{2}} \right)\Gamma (k - n + 1)}}
$$
The logarithmic derivative for $2\leq n\leq k$ satisfies
$$
\psi (k - n + 1) - \psi \!\left( {k - n + \tfrac{1}{2}} \right) - \psi (n) < \frac{2}{{k - n + 1}} - \log \left( {n - \tfrac{1}{2}} \right)<0,
$$
i.e., the sequence starts to decrease after $n=2$. For $n=1,2$ the terms of $(*)$ are
$$
\frac{{2k}}{{2k - 1}},\quad \frac{{2k(2k - 2)}}{{(2k - 1)(2k - 3)}}
$$
which are at most $2$, say, for large $k$. Thus,
$$
0 \leq \frac{1}{{2^n (n - 1)!}}\frac{{\Gamma (k + 1)\Gamma\! \left( {k - n + \frac{1}{2}} \right)}}{{\Gamma \!\left( {k + \frac{1}{2}} \right)\Gamma (k - n + 1)}} \le 2 \times \frac{1}{{2^n }}
$$
for all large $k$ and any $n\geq 1$. Consequently, we can apply Tannery's theorem and Stirling's formula, to deduce
\begin{align*}
& \mathop {\lim }\limits_{k \to  + \infty } \sum\limits_{n = 1}^k {\frac{1}{{2^n (n - 1)!}}\frac{{\Gamma (k + 1)\Gamma \!\left( {k - n + \frac{1}{2}} \right)}}{{\Gamma\! \left( {k + \frac{1}{2}} \right)\Gamma (k - n + 1)}}} 
\\ &
 = \sum\limits_{n = 1}^\infty  {\frac{1}{{2^n (n - 1)!}}\mathop {\lim }\limits_{k \to  + \infty } \frac{{\Gamma (k + 1)\Gamma \!\left( {k - n + \frac{1}{2}} \right)}}{{\Gamma \!\left( {k + \frac{1}{2}} \right)\Gamma (k - n + 1)}}}  = \sum\limits_{n = 1}^\infty  {\frac{1}{{2^n (n - 1)!}}}  = \frac{{\sqrt e }}{2}.
\end{align*}
A: We are interested in the asymptotics of
$$g(n) = \sum_{k=1}^{n-1} k {n\choose k}
\frac{(2n-2k-1)!!}{(2n-1)!!}
= n \sum_{k=1}^{n-1} {n-1\choose k-1}
\frac{(2n-2k-1)!!}{(2n-1)!!}.$$
Now we have
$$(2n-1)!! = \frac{(2n-1)!}{2^{n-1} \times (n-1)!}$$
so we get for our sum
$$\frac{n! \times 2^{n-1}}{(2n-1)!}
\sum_{k=1}^{n-1} {n-1\choose k-1}
\frac{(2n-2k-1)!}{2^{n-k-1} \times (n-k-1)!}
\\ = \frac{n! \times 2^{n-1}}{(2n-1)!}
\sum_{k=0}^{n-2} {n-1\choose k}
\frac{(2n-2k-3)!}{2^{n-k-2} \times (n-k-2)!}
\\ = \frac{n! \times 2^{n-1}}{(2n-1)!}
\sum_{k=0}^{n-2} {n-1\choose n-2-k}
\frac{(2k+1)!}{2^k \times k!}
\\ = 2^{n-1} {2n-1\choose n}^{-1}
\sum_{k=0}^{n-2} \frac{1}{(n-2-k)!} \frac{1}{2^k}
{2k+1\choose k}
\\ = 2^{n-1} {2n-1\choose n}^{-1} [z^{n-2}] \exp(z)
\sum_{k=0}^{n-2} z^k \frac{1}{2^k}
{2k+1\choose k}.$$
Here the coefficient extractor enforces the upper limit of the sum and
we obtain
$$2^{2n-2} {2n\choose n}^{-1} [z^{n-2}] \exp(z/2)
\sum_{k\ge 0} z^k \frac{1}{2^{2k}} {2k+1\choose k}$$
The sum is
$$-\frac{2}{z} + \frac{2}{z} \frac{1}{\sqrt{1-z}}.$$
We get from the first piece
$$-2^{2n-1} {2n\choose n}^{-1} [z^{n-1}] \exp(z/2)
= -2^{n} {2n\choose n}^{-1} \frac{1}{(n-1)!}$$
Now from the asymptotic ${2n\choose n}^{-1} \sim \sqrt{\pi n}/2^{2n}$ we
get for the modulus $\sqrt{\pi n}/2^n/(n-1)!$ so this vanishes quite
rapidly. Continuing with the second piece we obtain
$$2^{2n-1} {2n\choose n}^{-1}
[z^{n-1}] \frac{\exp(z/2)}{\sqrt{1-z}}.$$
We apply the Darboux method here as documented on page 180 section 5.3 of
Wilf's generatingfunctionology where we expand $\exp(z/2)$ about $1$
and take the first term, extracting the corresponding factor from the
singular term. This yields
$$\exp(1/2) \times 2^{2n-1} {2n\choose n}^{-1}
[z^{n-1}] \frac{1}{\sqrt{1-z}}
\\ = \exp(1/2) \times 2^{2n-1} {2n\choose n}^{-1}
{n-3/2\choose n-1}
\\ = \exp(1/2) \times 2^{2n-1} {2n\choose n}^{-1}
\frac{n}{n-1/2} {n-1/2\choose n}.$$
Using the Gamma function approximation of the second binomial
coefficient from the Wilf text we get
$$\exp(1/2) \times 2^{2n-1} {2n\choose n}^{-1}
\frac{n}{n-1/2} \frac{1}{\sqrt{n} \times \Gamma(1/2)}
\\ \sim \exp(1/2) \times 2^{2n-1}
\times \frac{\sqrt{\pi n}}{2^{2n}}
\frac{n}{n-1/2} \frac{1}{\sqrt{\pi n}}
\sim \frac{1}{2} \exp(1/2).$$
We have obtained
$$\frac{\sqrt{e}}{2}$$
the same as in the contributions that were first to appear.
