2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ the big parentheses enclose a ratio or a binomial coefficient? In the first case, why are they there? $\endgroup$ – Igor Rivin Dec 14 '13 at 22:44
  • $\begingroup$ @IgorRivin Thanks for spotting the typo. Fixed now. $\endgroup$ – user66307 Dec 14 '13 at 22:44
2
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Thomas Ahle Oct 19 '15 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy