<s>[INST] 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?
 [/INST] 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.
</s>