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$?

Question

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?

Answer 1

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*}

Answer 2

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.