Asymptotic upper bound for partial binomial-like sum

Question

I want to upper bound the quantity $$\sum_{i\le \alpha n} \binom{n}{i}\lambda^i$$, where ${\lambda>1}$, $0<\alpha<1$. It is not the same as partial sum of binomial coefficients. An asymptotic upper bound works for me. This answer provides an approximation, but I want an upper bound. I can use the last term approximation, but I want something that is simpler, as in not involving binomial coefficients.

Answer 1

Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have $$\sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}\quad (1) $$ where the upper bound approaches equality if $k$ and $n-k$ are both large. This is obtained from Stirling's approximation and then some other manipulation, and covers the whole range of $k$.

To only use the last term you can proceed as follows: If $\alpha\leq 1/2,$ let $k=\lceil \alpha n\rceil.$ If $\alpha>1/2$, let $k=\lfloor \alpha n\rfloor$ and use the difference $2^n$ minus the lower bound in (1).

This bounds the binomial, you may then just take the bound obtained above and multiply by $\lambda^{n \alpha}$ to obtain the overall bound (assuming $\lambda>1,$ else take the reciprocal. You can also replace the multiplicative terms under the square root with their maximal value over $0\leq k\leq \alpha n.$

A more careful approach would be to write $\lambda^k=\exp{\{k \ln \lambda\}}$ thus obtaining (ignoring the square roots) $\exp{\{n(h(k/n)+(k/n) \ln \lambda\}}$ for each term. This "tilted quantity" can then be maximized by differentiation over $\theta=k/n.$