3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How is that true ? for $f(100) \approx 10^{30} $ , please explain your computations $\endgroup$ – Ahmad Sep 20 '17 at 17:47
  • 1
    $\begingroup$ I added a bounty, and took the liberty to edit your question (and its tags). $\endgroup$ – Clement C. Sep 25 '17 at 22:43
  • $\begingroup$ I don't fully understand your summation notation here, my normal interpretation is that you would sum over all possibilities but that seems unlikely. my normal interpretation has led me to believe that that upperbound is much too low. can you explain what exactly you are summing over? $\endgroup$ – zen Sep 27 '17 at 15:44
  • 1
    $\begingroup$ $$\sum_{k=0}^{n-1}\sum_{j=0}^k$$ AFAICT. $\endgroup$ – Clement C. Sep 27 '17 at 15:50
4
+50
$\begingroup$

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). $$

$\endgroup$
  • $\begingroup$ You are right ! I finally figured out the sum and get the same answer. $\endgroup$ – Martin Chow Sep 28 '17 at 8:53
  • $\begingroup$ Can you post details of the derivation/proof, if any? (e.g., once conjectured, how do you prove your integral asymptotics holds?) $\endgroup$ – Clement C. Sep 28 '17 at 10:15
  • 1
    $\begingroup$ @ClementC., I elaborated my argument and gave a partial proof, with some step left unjustified. $\endgroup$ – Sangchul Lee Sep 28 '17 at 13:40
  • $\begingroup$ @SangchulLee Thank you for that. $\endgroup$ – Clement C. Sep 28 '17 at 13:42
1
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ Thank you all and this problem has been settled. $\endgroup$ – Martin Chow Sep 28 '17 at 8:52
1
$\begingroup$

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)"}]

Ration and Euler's constant

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

$\endgroup$
  • $\begingroup$ Just a remark: your plot seems to hint that $\lim_{n\to\infty}\frac{f(n)}{n\ln n+n} = \gamma$ which is equivalent to saying that $\lim_{n\to\infty}\frac{f(n)}{n\ln n} = \gamma$ (since $n=o(n\ln n)$). In other terms,the $+n$ term is irrelevant and this would suggest that $f(n)=\gamma n\ln n + o(n\ln n)$. $\endgroup$ – Clement C. Sep 28 '17 at 1:45
  • $\begingroup$ @ClementC. In the original extended comment I used the Mathematica command Plot rather than ListPlot which treated n as a continuous variable and hence the previous sawtooth plot. I've fixed that, included faster code, and extended the maximum value of n to 300. $\endgroup$ – JimB Sep 28 '17 at 6:10
  • $\begingroup$ Thank you all and this problem has been settled. $\endgroup$ – Martin Chow Sep 28 '17 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.