3
$\begingroup$

I'm trying to calculate the limit for the sum of binomial coefficients:

$$S_{n}=\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1} \right).$$

Numerically it seems to converge rapidly to zero and I have asked at https://math.stackexchange.com/questions/608296/limit-of-sum-i-1n-left-fracn-choose-i2in-sum-j-0i-i-choose but with no replies.

I tried applying Stirling's approximation and also using the fact that ${n \choose i} \leq 2^n/\sqrt{n}$ but that does not work well as the resulting function tends to infinity.

Please accept my apologies if this turns out to have a simple solution.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

By Stirling approximation for the central binomial coefficient, we have $$\sum_{j\le i}\binom ij^{n+1}\le(i+1)2^{i(n+1)}\left(\frac2{i\pi}\right)^{(n+1)/2},$$ hence $$S_n\le\frac n{2^{n-1}}+2\left(\frac2\pi\right)^{(n+1)/2}\sum_{i=2}^n\binom ni\frac{2^i}{i^{(n-1)/2}}.$$ Put $$c_i=\binom ni\frac{2^i}{i^{(n-1)/2}}.$$ For $i\ge2$, we have \begin{align*}\frac{c_{i+1}}{c_i}&=2\frac{n-i}{i+1}\left(1+\frac1i\right)^{-(n-1)/2}\\&\le2\frac{n-i}{i+1}\exp\left(-\frac{n-1}{2(i+1)}\right) =2\frac{n-i}{i+1}\exp\left(-\frac{n-i}{2(i+1)}-\frac{i-1}{2(i+1)}\right).\end{align*} Taking derivatives, we see that the function $f(x)=2xe^{-x/2}$ is maximized on $[0,+\infty)$ for $x=2$, and then it is decreasing. In particular, $f(x)\le12e^{-3}$ for $x\ge6$. Since $-(i-1)/2(i+1)=-1/2+O(1/n)$ for $i\ge n/7$, and $4e^{-3/2},12e^{-3}<9/10$, we obtain $$\frac{c_{i+1}}{c_i}\le\frac9{10}$$ for all $i$. Thus, $S_n$ is bounded by a geometric series, and specifically, \begin{align*} S_n&\le\frac n{2^{n-1}}+20\left(\frac2\pi\right)^{(n+1)/2}c_2\\ &\le\frac n{2^{n-1}}+40\left(\frac2\pi\right)^{(n+1)/2}\frac{n^2}{2^{(n-1)/2}}=O(n^2\pi^{-n/2}). \end{align*}

Improve this answer
$\endgroup$
9
  • $\begingroup$ For more precise asymptotics, the first two terms in the sum are of the order $n2^{n-1}$ and $n^22^{-n}$, and the rest is bounded by the argument I gave by $O(c_3(2/\pi)^{n/2})=O(n^3(2/3\pi)^{n/2})=o(2^{-n})$, hence $S_n\sim n^22^{-n}$. $\endgroup$
    – Emil Jeřábek
    Commented Dec 18, 2013 at 14:49
  • 1
    $\begingroup$ Need 7/e^2, not 8/e^2. e^2 < 8. $\endgroup$
    – The Masked Avenger
    Commented Dec 18, 2013 at 15:19
  • $\begingroup$ Something feels wrong. (Possibly I am misreading.) Your claim that for large n the c_i decrease as i increases suggests that for large n, the ith term of the outer sum decreases as i decreases. This is true at some point, but only after i > n/2, not for all i. I suspect the c_i behave not as nicely as you describe, either in monotonicity, or in being a factor of an upper bound. $\endgroup$
    – The Masked Avenger
    Commented Dec 18, 2013 at 16:53
  • $\begingroup$ Here is the intuition I have. Let the sum of n+1th powers be d_i. As i increases, all but two of the (roots of the) summands in d_i almost double, so d_i goes up by almost 2^(n+1). This to me means (n choose i) d_i/2^(in) for i between n/2 and 2n/3. Again I may have made a mistake, but the n^2/pi^n/2 order does not seem to hit the mark $\endgroup$
    – The Masked Avenger
    Commented Dec 18, 2013 at 17:15
  • 1
    $\begingroup$ As I wrote in the first comment, the true bound is $S_n\sim n^22^{-n}$. $\endgroup$
    – Emil Jeřábek
    Commented Dec 18, 2013 at 21:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .