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.

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

2 Answers 2

up vote 2 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|improve this answer

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|improve this answer

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.