Lower/Upper bounds for $ \sum\limits_{i=0}^k \binom ni x^i $

Question

Are there good lower/upper bounds for $ \sum\limits_{i = 0}^k {\left( \begin{array}{l} n \\ i \\ \end{array} \right)x^i } $ where $0<x<1$, $k \ll n$?

Answer 1

Write $x=p/(1-p)$ and then $$ \sum_{i=0}^k \binom ni x^i = (1-p)^{-n}\sum_{i=0}^k \binom ni p^k(1-p)^{n-k}.$$ The last sum is the cumulative binomial distribution, which has no exact formula (except as a special function) but a large literature on bounds. It is quite a common topic on Mathoverflow, see these for example: ref1 ref2 ref3 ref4 ref5

Answer 2

Let $p=\frac{x}{1+x}$ and $q=\frac{1}{1+x}$, and thus $$\sum_{i=0}^k \binom{n}{i} x^i=(1+x)^n\sum_{i=n-k}^n \binom{n}{i} p^{n-i} q^i.$$ Then for $k<np$ Chernoff bound gives $$\sum_{i=n-k}^n \binom{n}{i} p^{n-i} q^i \le \left( \frac{nq}{n-k}\right)^{n-k} e^{np-k}.$$ That is, $$\sum_{i=0}^k \binom{n}{i} x^i \le (1+x)^k \left( \frac{n}{n-k}\right)^{n-k} e^{\frac{(n-k)x-k}{1+x}}.$$

Answer 3

Hint :for lower Bound we have for $k> 1$:$ (1+\frac{1}{k})^k \leq (e^{1/k})^k =e ,0<x=1/k<1$ , and $1/k << k $