1
$\begingroup$

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 :-(
$\endgroup$
0
$\begingroup$

Handy hint. You can use special functions for the lower bound. Indeed, the equation \begin{equation} y = a x - x \ln x \end{equation} with $x=k+1$, $y=m \ln 2$ and $a=\ln n$, rewrites as \begin{equation} -y\, \text{e}^{-a} = \left(\ln x - a\right) \text{e}^{\ln x - a} \, , \end{equation} 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 \begin{equation} k+1 = n\exp\left(W\!\left(-\frac{m \ln 2}{n}\right)\right)\, . \end{equation}

$\endgroup$

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.