4
$\begingroup$

If we define

$$ S = \sum_{k=1}^{\lceil n/2 \rceil} \binom n k \left(\frac{k}{n}\right)^{2k} \left(1 - \frac{k}{n}\right)^{2(n-k)} $$

Then when $n\to \infty$, does $S \to 0$?

  • 4
    I'm now mildly curious as to where you're getting these expressions you're asking us to peer at...2011-10-10
  • 0
    I'm taking a course of random graph. The exercises are really difficult. Sometimes no students in class could solve all of them. These equations are the best I can reach. If I can get $S \to 0$ then I'm done. But I've completely no idea if this is the correct direction or it's a just another dead end.2011-10-10
  • 0
    If the sequence is always positive, there's no way the sum can be zero. Since $k, $1-\tfrac k n>0$ and this was the only chance of getting negative terms...2011-10-10
  • 0
    @process91, think about this sum, $\sum_{k=1}^{\lceil n/2 \rceil} (1-p)^{k(n-k)}$. Erdos has proved it goes to 0, if $p = c \log n / n, c > 1$. I'm actually trying to mimic what he did : http://www.renyi.hu/~p_erdos/1961-15.pdf2011-10-10
  • 0
    A point of English grammar: One says "This sum goes to zero" or "Does this sum go to zero?" but never "Does this sum goes to zero?"; similarly "This sum went to zero" or "Did this sum go to zero?", but never "Did this sum went to zero?". Many times I've noticed French-speaking people getting confused about this. I fixed the title.2011-10-10
  • 0
    @process91: It's a little more subtle than that, in general since everything is a function of $n$. Consider, for example $S_n = \sum_{k=1}^n n^{-2-\epsilon} k$.2011-10-10
  • 0
    Of course I could be wrong. It indeed might not go to 0. But that means I wasted another half a day on this problem.2011-10-10
  • 0
    @cardinal: OK, I got it now. That confused me for a minute, but I see now that since the terms change depending on the value of $n$, that all the terms may go to zero.2011-10-10
  • 0
    It seems like this result should have some combinatoric/probabilistic interpretation, perhaps in terms of the central limit theorem. Hopefully an expert like @DidierPiau can shed some light.2011-10-11

1 Answers 1

4

There is the answer, and then there is getting to the answer. I'll give a proof, and then I'll try to give some of my thought process.

Yes, $S \to 0$. Let $$A(k,n) = \binom{n}{k} \left( \frac{k}{n} \right)^{2k} \left( \frac{n-k}{n} \right)^{2(n-k)}.$$ Then $$\frac{A(k,n)}{A(k-1,n)} = \frac{n-k+1}{k} \frac{k^{2k}}{(k-1)^{2k-2}} \frac{(n-k)^{2(n-k)}}{(n-k+1)^{2n-2k+2}}$$ $$=\frac{k^{2k-1}}{(k-1)^{2k-2}} \frac{(n-k)^{2n-2k}}{(n-k+1)^{2n-2k+1}} = \frac{k}{n-k} \frac{(1+1/(k-1))^{2k-2}}{(1+1/(n-k))^{2n-2k}}$$ $$\approx \frac{k}{n-k} \frac{e^2}{e^2} = \frac{k}{n-k} < 1$$

Leaving it to you to make the bounds rigorous, this shows that $A(k,n)$ is a descreasing function of $k$.

Now, $A(2,n) = \binom{n}{2} 16/n^4 (1-2/n)^{2n-4} \leq (n^2/2) (16/n^4) = 8/n^2$. So the entire sum is $$\leq A(1,n) + (n/2 -1) A(2,n) \leq n \cdot n^{-2} (1-1/n)^{2n-2} + (n/2) (8/n^2) \leq n^{-1} + 4 n^{-1}$$ and this goes to zero.


So, how did I think about this? I took logs of everything. $\log \binom{n}{k} \approx k \log (n/k) + (n-k) \log (n/(n-k))$. I knew this but, if I hadn't, it follows from Stirling's approximation. So $\log A(k,n) \approx - k \log (n/k) - (n-k) \log (n/(n-k))$. So, when $k$ was of the same scale as $n$ (say $k > 0.01 n$), the summand $A(k,n)$ would be exponentially small. That suggested what I should do was look very carefully at the first few values of $k$, and everything else would drop out.

For $k$ a fixed small integer, I had $A(k,n) \approx (n^k/k!) k^{2k}/n^{2k} = n^{-k} (\mbox{constant})$. So any individual small $k$ term would be negligible as $n \to \infty$.

So then I had find some argument to close the gap between fixed $k$ and $k=0.01 n$. At this point, I'm not sure there is any big lesson to give, except that taking ratios of consecutive terms is often a good idea. The key point is that I already knew, from my earlier nonrigorous computations, that I expected a rapid drop off near $k=0$.