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.

  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 27 '18 at 18:20
  • 1
    $\begingroup$ You can get a fairly decent upper bound minimizing $[x^{-\alpha}(1+\lambda x)]^n$ over $x\in[0,1]$. $\endgroup$ – 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.$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.