Maple seems to suggest that for any real $a\ge 1$ and positive integer $K$ and $n$ with $K\le n/(a+1)$ one has
 $$ a^n + na^{n-1} + \binom{n}{2}a^{n-2} +...+ \binom{n}{K}a^{n-K} \le a^{n-K} e^{nH(K/n)}, $$
where $H(x)=-x\log(x)-(1-x)\log(1-x)$ is the entropy function.


An essentially equivalent form is as follows. Suppose that $X\sim B(n,p)$, where $p<1/2$, and let $q:=1-p$. Then for any $\alpha\le 1$,
 $$ \mathsf{Pr}(X\le\alpha pn) \le p^{\alpha pn}q^{(1-\alpha p)n}e^{nH(\alpha p)}. $$


I believe this should be well-known (if at all true). Can anybody suggest a reference?



A large deviation / binomial coefficients bound
After a little thinking, there is a strikingly simple proof, running as follows.


Dividing through both sides of the inequality by $a^{n-K}$, we see that the larger is $a$, the stronger the estimate is. Thus, the general case will follow from that where $K=n/(a+1)$. For brevity we write $p:=K/n$ and $q:=1-p$, so that $a=q/p$ and $a+1=p^{-1}$. The inequality in question can now be re-written as 
 $$ \sum\_{j=0}^K \binom nj a^{n-j} \le a^{qn} e^{nH(p)}. $$
Since the left-hand side does not exceed $(a+1)^n=p^{-n}$, it suffices to show that
 $$ p^{-n} \le a^{qn} e^{nH(p)}; $$
that is, 
 $$ p^{-n} a^{-qn} \le e^{nH(p)}. $$
However, the left-hand side is equal to
 $$ p^{-n} (q/p)^{-qn} = p^{-pn} q^{-qn} = e^{nH(p)}, $$
which completes the proof.




---


Although the proof is almost vacuous, the inequality is surprisingly sharp: numerical computations suggest that the right-hand side is always at most twice larger than the left-hand side.


