# Upper bound for sum

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.

• 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. – user66307 Dec 14 '13 at 22:44

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

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

• 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