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.

$\endgroup$
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*}

$\endgroup$
  • $\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 Dec 18 '13 at 14:49
  • 1
    $\begingroup$ Need 7/e^2, not 8/e^2. e^2 < 8. $\endgroup$ – The Masked Avenger Dec 18 '13 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 Dec 18 '13 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 Dec 18 '13 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 Dec 18 '13 at 21:25

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.