show/hide this revision's text 3 deleted 3 characters in body

After a little thinking, there is a strikingly simple proof, running as follows.

Dividing through both sides of the inequality by 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.
show/hide this revision's text 2 added 132 characters in body

After a little thinking, this actually does not have much to do with large deviations, and there is an almost trivial a strikingly simple proof, running as follows.

Dividing through both sides of the inequality by 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.
show/hide this revision's text 1

After a little thinking, this actually does not have much to do with large deviations, and there is an almost trivial proof, running as follows.

Dividing through both sides of the inequality by 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.