# Asymptotic upper bound for partial binomial-like sum

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.

• You can also try approximating by a geometric series with a coefficient that is an upper bound on any binomial terms that you do not want to see. A good upper bound will depend heavily on $\alpha, \lambda,$ and $n$, but if you just need an upper bound you can likely find a simple and pleasing expression. Gerhard "There's Always $(1 + \lambda)^n$ " Paseman, 2018.11.27. – Gerhard Paseman Nov 27 '18 at 18:20
• You can get a fairly decent upper bound minimizing $[x^{-\alpha}(1+\lambda x)]^n$ over $x\in[0,1]$. – fedja Nov 27 '18 at 19:47

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