5
$\begingroup$

It is known that $\sum_{i=1}^n {n \choose i}=2^n$. I am wondering what would be the sum if we change the upper limit to $\sqrt n/2$, i. e. How to calculate$\sum_{i=1}^{[\frac{\sqrt n}{2}]}{n \choose i}?$

  • 0
    It might be difficult to evaluate the exact sum. But you can get a good asymptotic using Stirling's approximation and a handle on the error using Euler–Maclaurin and chebyshev inequality. – 2012-04-30

1 Answers 1

2

The terms in the sum grow rapidly, and for large $n$, the last term is much larger than all others. The approximate answer is therefore $\binom{n}{\sqrt{n}/2}$ and the first $k$ terms of an asymptotic expansion can be had by adding the last $k$ terms in the sum. Exact formulas to simplify the sum do not exist.