Return to Revisions

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