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