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}?$
Calculate $\sum_{i=1}^{[\frac{\sqrt n}{2}]}{n\choose i}$
5
$\begingroup$
combinatorics
sequences-and-series
statistics
binomial-coefficients
-
0It 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
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.