Asymptotics of $\sum_{0 \leq j \leq k \leq n-1} {\binom{2n}{j}}{\binom{2n-1}{k}}^{-1}$ For any integer $n\geq 1$, define $$f(n) = \sum_{0 \leq j \leq k \leq n-1} \frac{\binom{2n}{j}}{\binom{2n-1}{k}}$$ Our lecture says that $f(n) = n +n\log n +O(1)$. But I cannot prove it, the best result I've gotten is $f(n) \leq cn^{\frac{3}{2}}$, and now I'm kind of doubtful about the result. Is it possible to prove it or deny it?
 A: 
Conjecture. As $n\to\infty$, we have
$$ f(n) = \frac{1}{2}n\log n + \left(\frac{\gamma}{2}+\log 2 \right) n + o(1).$$

A partial proof. Write
$$ f(n) = 2n \sum_{j=0}^{n-1} \binom{2n}{j} \sum_{k=j}^{n-1} \frac{(2n-1-k)!k!}{(2n)!}. \tag{1}$$
We first find an integral represtentation of the inner sum. Utilizing the gamma integral,
\begin{align*}
\sum_{k=j}^{n-1} \frac{(2n-1-k)!k!}{(2n)!}
&= \sum_{k=j}^{n-1} \frac{1}{(2n)!}\int_{0}^{\infty} \int_{0}^{\infty} x^{2n-1-k}y^k e^{-(x+y)} \, dxdy \\
&= \frac{1}{(2n)!} \int_{0}^{\infty} \int_{0}^{\infty} x^{2n-1} \left( \sum_{k=j}^{n-1} (y/x)^k \right) e^{-(x+y)} \, dxdy\\
&= \frac{1}{(2n)!} \int_{0}^{\infty} \int_{0}^{\infty} \frac{x^{2n-j}y^j - x^n y^n}{x - y} e^{-(x+y)} \, dxdy.
\end{align*}
Now make the substitution $(r, p) = (x+y, \frac{x}{x+y})$. Then we have $dxdy = r dr dp$ and
\begin{align*}
&= \frac{1}{(2n)!} \int_{0}^{1} \int_{0}^{\infty} r^{2n} e^{-r} \frac{p^{2n-j}(1-p)^j - p^n(1-p)^n}{2p - 1} \, drdp \\
&= \int_{0}^{1} \frac{p^{2n-j}(1-p)^j - p^n(1-p)^n}{2p - 1} \, dp \\
\small[\text{substitute }s = 1-2p] \quad &= \frac{1}{2^{2n+1}} \int_{-1}^{1} \frac{(1-s^2)^n - (1-s)^{2n-j}(1+s)^j}{s} \, ds
\end{align*}
Now using the symmetry, we know that
$$ \int_{-1}^{1} \frac{1 - (1-s^2)^n}{s} \, ds = 0. $$
Adding the above integral to our final integral, we obtain
$$ \sum_{k=j}^{n-1} \frac{(2n-1-k)!k!}{(2n)!}
= \frac{1}{2^{2n+1}} \int_{-1}^{1} \frac{1 - (1-s)^{2n-j}(1+s)^j}{s} \, ds. $$
Plugging this whole sum back to the first identity $\text{(1)}$ yields
\begin{align*}
f(n)
&= n \sum_{j=0}^{n-1} \binom{2n}{j} \frac{1}{2^{2n}} \int_{-1}^{1} \frac{1 - (1-s)^{2n-j}(1+s)^j}{s} \, ds \\
&= n \sum_{j=n+1}^{2n} \binom{2n}{j} \frac{1}{2^{2n}} \int_{-1}^{1} \frac{1 - (1-s)^{j}(1+s)^{2n-j}}{s} \, ds \\
&= n \mathbb{E} \left[ \int_{-1}^{1} \frac{1 - (1-s)^{N}(1+s)^{2n-N}}{s} \, ds \ ; \ N > n\right], \tag{2}
\end{align*}
where $N$ is a random variable having binomial distribution $\operatorname{Bin}(2n,\frac{1}{2})$. To compute the inner integral, we perform integration by parts:
\begin{align*}
&\int_{-1}^{1} \frac{1 - (1-s)^{N}(1+s)^{2n-N}}{s} \, ds \\
&\hspace{1.5em} = \left[ \vphantom{\int} \left( 1 - (1-s)^{N}(1+s)^{2n-N} \right) \log(\sqrt{n}|s|) \right]_{s=-1}^{s=1} \\
&\hspace{4em} + \int_{-1}^{1} \Big\{ (2n-N)(1-s)^{N}(1+s)^{2n-N-1} \\
&\hspace{6.5em} - N (1-s)^{N-1}(1+s)^{2n-N} \Big\} \log(\sqrt{n}|s|) \, ds \\
&\hspace{3em} = 2^{2n-1} (\log n) \mathbf{1}_{\{N = 2n\}} \\
&\hspace{5.5em} - \int_{-1}^{1} \frac{2(N-n+ns)}{1-s^2}(1-s)^{N}(1+s)^{2n-N}  \log(\sqrt{n}|s|) \, ds.
\end{align*}
To compute the last line, we apply substitutions $N = n + \sqrt{\smash[b]{n/2}} \, Z$ and $s = t/\sqrt{n}$. Then $\text{(2)}$ simplifies to
\begin{align*}
f(n)
&= \frac{1}{2}n \log n \\
&\hspace{1em} - 2n \underbrace{ \mathbb{E} \Bigg[ \int_{-\sqrt{n}}^{\sqrt{n}} \left(\frac{Z}{\sqrt{2}}+t \right)\left(1 - \frac{t^2}{n}\right)^{n-1} \left( \frac{1 - \frac{t}{\sqrt{n}}}{1 + \frac{t}{\sqrt{n}}} \right)^{\sqrt{\smash[b]{n/2}} \, Z} \log|t| \, dt \, ; \, Z > 0 \Bigg] }_{=\text{(*)}}
\end{align*}
Now we make a bit of loose computation. Let $n \to \infty$ to the inner integral and notice that the integrand converges pointwise nicely. Also, the classical CLT tells that $Z$ converges in distribution to the standard normal distribution and this convergence is not wild. So it is tempting to believe that the whole expectation $\text{(*)}$ also converges to
$$ \text{(*)} \xrightarrow[n\to\infty]{\text{let's believe!}}
\mathbb{E} \Bigg[ \int_{-\infty}^{\infty} \left(\frac{Z}{\sqrt{2}}+t \right)e^{-t^2 - \sqrt{2}Zt} \log|t| \, dt \, ; \, Z > 0 \Bigg], \tag{3}
$$
where now $Z$ has standard normal distribution. (I am kind of sure that this can be justified with some hard analysis, though I do not want to spare much time on this.) Computing the outer expectation first,
$$ \text{[RHS of (3)]}
= \int_{-\infty}^{\infty} \frac{e^{-t^2} \log|t|}{2\sqrt{\pi}} \, dt
= -\frac{1}{4} (\gamma + 2\log 2). $$
Therefore, modulo the claim $\text{(3)}$ we have proved that
$$ f(n) = \frac{1}{2}n\log n + \left( \frac{\gamma}{2} + \log 2 \right)n + o(n). $$
A: We have $\sum \limits_{k=0}^{n-1} \sum \limits_{j=0}^{k} \frac{\binom{2n}{j}}{\binom{2n-1}{k}} = \sum \limits_{k=0}^{n-1} \sum \limits_{j=0}^{k} \frac{\frac{(2n)!}{j! (n-j)!}}{\frac{(2n-1)!}{k! (2n-1-k)!}} = 2n \sum \limits_{k=0}^{n-1} \sum \limits_{j=0}^{k} \frac{k! (2n-1-k)!}{j! (2n-j)!}$
When $j=k$ the expression $\frac{k! (2n-1-k)!}{j! (2n-j)!}$ becomes $\frac{1}{2 n-k}$
When $j=k-1$  the expression $\frac{k! (2n-1-k)!}{j! (2n-j)!}$ becomes $\frac{k}{(2 n-k) (-k+2 n+1)} < \frac{k}{(2n-k)^2}$
When $j=k-2$ the expression $\frac{k! (2n-1-k)!}{j! (2n-j)!}$ becomes $\frac{(k-1) k}{(2 n-k) (-k+2 n+1) (-k+2 n+2)} < \frac{k^2}{(2n-k)^3}$
its obvious from here that $\sum \limits_{j=0}^{k} \frac{k! (2n-1-k)!}{j! (2n-j)!} < \sum \limits_{j=0}^{k} \frac{k^j}{(2n-k)^{j+1}}  <\sum \limits_{j=0}^{\infty} \frac{k^j}{(2n-k)^{j+1}} =\frac{1}{2 (n-k)} $
So $\sum \limits_{k=0}^{n-1} \sum \limits_{j=0}^{k} \frac{\binom{2n}{j}}{\binom{2n-1}{k}}  < 2n \sum \limits_{k=0}^{n-1} \frac{1}{2(n-k)} = 2n *\frac{1}{2} \sum \limits_{k=0}^{n-1} \frac{1}{n-k} = n H_n < n( \ln n +\gamma +\frac{1}{2n})$.
So the upper bound is $n \ln n + \gamma n +O(1)$ where $\gamma \approx 0.577$ is Euler Constant.
Check again with your lecture because $f(n) < n\ln n+\gamma n+O(1)$ and since $\gamma \approx 0.577 <1$ ,
$f(n)$ can not be equal to $n \ln n +n +O(1)$.
This is as far as i can go, giving you the exact summation up to $O(1)$ is too hard for me :)
A: Just an extended comment.  Plotting $f(n)/(n+n \ln{n})$ and Euler's constant for $n=1$ to $n=300$ shows the following (using Mathematica):
The inner sum can be simplified somewhat:
Sum[Binomial[2 n, j], {j, 0, k}]
(* 4^n - Binomial[2 n, 1 + k] Hypergeometric2F1[1, 1 + k - 2 n, 2 + k, -1] *)

So the figure can be generated a bit quicker with
f[n_] := Sum[(4^n - Binomial[2 n, 1 + k] Hypergeometric2F1[1, 1 + k - 2 n, 2 + k, -1])/
  Binomial[2 n - 1, k], {k, 0, n - 1}]

xy = Table[{n, N[f[n]/(n + n Log[n])]}, {n, 1, 300}];
ListPlot[{xy, {{0, EulerGamma}, {300, EulerGamma}}}, Joined -> {False, True}, 
PlotLegends -> {"f(n)/(n+n*ln(n))", "Euler's constant"},
AxesLabel -> {"n", "f(n)/(n+n*ln(n)"}]


So...maybe Euler's constant might not be the limiting constant.
