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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to get an upper bound the following sum: $$S_{n,r}=\sum_{i=0}^n \binom{n}{i} \left(\frac{\binom{n}{i}}{2^n}\right)^{r} .$$

Any hints would be greatly appreciated. I thought of using Stirling's approximation but I worried that doesn't give good bounds for binomial coefficients over the full range.

share|cite|improve this question
1  
the big parentheses enclose a ratio or a binomial coefficient? In the first case, why are they there? – Igor Rivin Dec 14 '13 at 22:44
    
@IgorRivin Thanks for spotting the typo. Fixed now. – Lembik Dec 14 '13 at 22:44
up vote 3 down vote accepted

Actually, you can do a lot better than @Xoff, since $$\binom{n}{i} \leq 2^n/\sqrt{n}$$, so $$S_{n, r} \leq 2^n/n^{r/2}.$$

share|cite|improve this answer
    
This is less sharp, so I wouldn't call it "A lot better". – Thomas Ahle Oct 19 '15 at 8:42
    
How do you know Xoff did not modify his answer after I posted mine? – Igor Rivin Oct 19 '15 at 9:31

As $\binom{n}{i}\le 2^n$, $$S_{n,r}\le\sum_{i=0}^n\binom{n}{i}.1^r=2^n$$

if you want something better you can use $\binom{n}{i}\le\binom{n}{p}$ (with $p=\lfloor\frac{n}{2}\rfloor$).

Hence $$S_{n,r}\le 2^n\left(\frac{\binom{n}{p}}{2^n}\right)^r$$

So $\lim_{r\rightarrow\infty}S_{n,r}=0$.

share|cite|improve this answer
    
If we use ${2n\choose n}\approx 4^n/\sqrt{\pi n}$ we can approximate this as $2^n/(\pi n/2)^{r/2}$. This is similar to Igor, and still an upper bound to $S_{n,r}$. – Thomas Ahle Oct 19 '15 at 9:02

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.