Solving inequality with partial sum of binomial coefficient

Given an integer $n$ and another one $m \leq n$, I am trying to get a tight upper and lower bound for the parameter $k \leq n$ such that the following inequality involving a partial sum with binomial coefficients (let's say "binomial partial sum") holds: $$\sum\limits_{i=0}^{k} {{n}\choose{i}} \leq 2^m \leq \sum\limits_{i=0}^{k+1} {{n}\choose{i}}$$

That is to say : the largest $k$ up to which the binomial partial sum is the closest to $2^m$

I have already found a trivial upper bound (see below), but it seems very rough... And I keep failing for the lower bound.

My question : Is it possible to get a tighter upper bound and a tight lower bound ?

Trivial upper bound

To get a trivial upper bound for $k$ :

• we consider the known upper bound $\sum\limits_{i=0}^{p} {{n}\choose{i}} \leq (n+1)^{p}$ for the binomial partial sum
• we rewrite the equation by using this bound in order to get what we want :

$$\sum\limits_{i=0}^{k} {{n}\choose{i}} \leq (n+1)^{k} \leq 2^m$$

• Which leads to the following upper bound :

$$k \leq \frac{m}{\log(n+1)}$$

Trivial lower bound (fail)

To get a trivial lower bound for $k$ :

• we consider the known lower bound ${(\frac{n}{p})}^{^p} \leq {{n}\choose{p}}$ for the binomial coefficient which leads also to ${(\frac{n}{p})}^{^p} \leq \sum\limits_{i=0}^{p} {{n}\choose{i}}$ for the binomial partial sum
• we rewrite the equation by using this bound in order to get what we want :

$$2^m \leq {(\frac{n}{k+1})}^{^{k+1}} \leq \sum\limits_{i=0}^{k+1} {{n}\choose{i}}$$

• which leads to : $$m \leq (k+1)\log (n) - (k+1)\log (k+1)$$
• But I'm stuck here : I fail in grouping the $k$ together :-(

1 Answer

Handy hint. You can use special functions for the lower bound. Indeed, the equation $$y = a x - x \ln x$$ with $x=k+1$, $y=m \ln 2$ and $a=\ln n$, rewrites as $$-y\, \text{e}^{-a} = \left(\ln x - a\right) \text{e}^{\ln x - a} \, ,$$ which is of the form $Y = X \text{e}^X$. The solutions of such equations are given by $X = W(Y)$, where $W$ denotes the Lambert $W$-function (see e.g. the Wikipedia page). Thus, the equality case of the lower bound is $$k+1 = n\exp\left(W\!\left(-\frac{m \ln 2}{n}\right)\right)\, .$$