8
$\begingroup$

What is $$\lim_{n\to\infty} \displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\left(4^{-k}\binom{2k}{k}\right)^{\frac{2n}{\log_2{n}}}\,?$$

$\endgroup$
6
  • 1
    $\begingroup$ Do you mean $\log_2n = (\log n)/(\log 2)$ or $\log_2 n = \log\log n$? $\endgroup$ Commented Apr 12, 2014 at 18:59
  • $\begingroup$ @GregMartin Very much the former. The constant factor seems to make a difference as to whether it converges or not. $\endgroup$
    – Simd
    Commented Apr 12, 2014 at 19:06
  • $\begingroup$ I observe that the summand seems to peak around $k \sim n/(\log_2 n\cdot \log\log n)$, so working out how big it is there would be useful. $\endgroup$ Commented Apr 12, 2014 at 19:08
  • $\begingroup$ It can be show that in Maple soft, your limit is unbounded. $\endgroup$
    – user48365
    Commented Apr 12, 2014 at 20:58
  • 2
    $\begingroup$ Given S. Carnahan's answer, it's clear that this really is a borderline case that's extremely interesting. Kudos for posing an insightful problem! $\endgroup$ Commented Apr 15, 2014 at 18:55

1 Answer 1

10
$\begingroup$

First, we note that Stirling's series yields $4^{-k} \binom{2k}{k} = \frac{1}{\sqrt{\pi k}}e^{-1/8k + O(k^{-3})}$.

Let $c = k/n$. Then

  1. $\log n!$ expands as $n \log n - n + O(\log n)$.
  2. $\log (2k)!$ expands as $2cn \log 2cn - 2cn + O(\log n)$.
  3. $\log(n-2k)!$ expands as $n(1-2c)(\log n + \log(1-2c)) - n(1-2c) + O(\log n)$.
  4. $\log \binom{n}{2k}$ expands as $-2cn\log 2c - n(1-2c) \log (1-2c) + O(\log n)$. This is $n$ times the following function of $2c$: graph of (1-2c)log(1-2c)+2c log 2c
  5. $\frac{2n \log 2}{\log n} \log\left(\frac{1}{\sqrt{\pi k}}e^{-1/8k + O(k^{-3})}\negthinspace\right)$ expands as $\frac{n \log 2}{\log n}(-\log n -\log c -\log \pi) - O(\frac{1}{c\log n})$

We need to consider the asymptotics of the sum of the 4th and 5th terms. The 5th term is dominated by $-n \log 2$, unless $c\sim 1/n$ (i.e., $k\sim 1$ - a short calculation shows we don't need to worry about this case). From calculus (or brief examination of Pascal's triangle) the fourth term achieves its maximum value of $n \log 2$ at $c=1/4$. The sum is then dominated by the term $\frac{n \log 2}{\log n}(-\log c -\log \pi)$. Since $\pi c = \pi/4 < 1$, we have $(-\log c -\log \pi)>0$, so the sum $\frac{n \log 2}{\log n}(-\log c -\log \pi) + O(\log n)$ increases without bound.

In conclusion, the sum diverges, because the summand for $k = \lfloor \frac{n}{4} \rfloor$ increases without bound as $n$ increases.

$\endgroup$
6
  • $\begingroup$ Is the OP right that convergence depends on the constant in the exponent? I can't immediately tell from your answer. $\endgroup$
    – Simd
    Commented Apr 13, 2014 at 10:51
  • 1
    $\begingroup$ @Anush Yes. In the fourth expansion of my list, the optimal coefficient of $n$ is about $0.14676$, and the coefficient of $n$ from the fifth sum is $-\log 2$. Thus, if you divide the exponent by more than about 4.722967, the limit diverges. [Edit: this is not accurate - see later comments.] $\endgroup$
    – S. Carnahan
    Commented Apr 13, 2014 at 14:11
  • $\begingroup$ Shouldn't the function in (4) be $n$ times $-2c\log2c - (1-2c)\log(1-2c)$ rather than $-2c\log2c + (1-2c)\log(1-2c)$? $\endgroup$ Commented Apr 14, 2014 at 7:21
  • $\begingroup$ @GregMartin You're right, thanks. I've made quite a mess of this question. $\endgroup$
    – S. Carnahan
    Commented Apr 15, 2014 at 5:00
  • 1
    $\begingroup$ @Anush Yes. The OP's exponent is precisely what is needed to cancel the $n \log 2$ from $\log \binom{n}{2k}$ for optimal $k$. This is why I needed to consider the sub-leading term with the $\pi c$ computation. If the exponent is smaller, the sums diverge even more wildly, and if the exponent is larger, the sums converge to 1. $\endgroup$
    – S. Carnahan
    Commented Apr 15, 2014 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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