Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
4  
I'm now mildly curious as to where you're getting these expressions you're asking us to peer at... –  J. M. Oct 10 '11 at 16:00
    
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. –  ablmf Oct 10 '11 at 16:07
    
If the sequence is always positive, there's no way the sum can be zero. Since $k<n$, $1-\tfrac k n>0$ and this was the only chance of getting negative terms... –  Michael Boratko Oct 10 '11 at 16:13
    
@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 : renyi.hu/~p_erdos/1961-15.pdf –  ablmf Oct 10 '11 at 16:24
    
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. –  Michael Hardy Oct 10 '11 at 16:25
show 4 more comments

1 Answer

up vote 4 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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