3

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.

1 Answers1

4

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*}

  • 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}$. – Emil Jeřábek Dec 18 '13 at 14:49
  • 1
    Need 7/e^2, not 8/e^2. e^2 < 8. – The Masked Avenger Dec 18 '13 at 15:19
  • 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. – The Masked Avenger Dec 18 '13 at 16:53
  • 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 – The Masked Avenger Dec 18 '13 at 17:15
  • The $c_i$ are an upper bound (and not terribly accurate at that for small $i$), I am not claiming that the terms in the original sum are decreasing. Having said that, I think that they are actually decreasing, and much faster than a geometric series, as long as you take them by steps of two (it is easy to see that for small $i$, the $2i$th term is asymptotically larger than the $(2i-1)$th term by a factor of about $n/4i$ , but the $(2i+1)$th term is smaller than the $2i$th by an exponential factor). – Emil Jeřábek Dec 18 '13 at 17:16
  • I don’t understand your last comment, in particular the part from “This to me“ to the next period does not seem to be a finished sentence. A rough calculation shows that the $n/2$th term of the original sum is, up to a polynomial factor, of the order $(32/\pi n)^{-n/2}$. Due to the $n$ in the denominator, this is much smaller than the $(18/10\pi)^{n/2}$ bound that I am claiming for this term. – Emil Jeřábek Dec 18 '13 at 17:35
  • Sorry I am using a phone with small screen, and sometimes miss out on some needed edits. The intended meaning is that for fixed n, the value inside the big parens goes up as i goes from 1 to about n/2, and does not go down again until some i > n/2. But I may have miscalculated. Until I can point at a specific error in the current version, (or in my thinking,) I will have to cope with this sense of something wrong. – The Masked Avenger Dec 18 '13 at 17:45
  • The key word is the “almost” in “summands in $d_i$ almost double”. You actually save a factor of $\sqrt{1+1/i}$, which looks negligible, but blows up to $\exp(n/2i)$ upon raising it to the $(n+1)$th power. This is quite enough to overcome the $2n/i$ or so increase you get by the rest of your argument. – Emil Jeřábek Dec 18 '13 at 17:57
  • 1
    As I wrote in the first comment, the true bound is $S_n\sim n^22^{-n}$. – Emil Jeřábek Dec 18 '13 at 21:25