We have the following inequality:

$$2^x \leq \sum_{i=0}^m{{x \choose i}\lambda^i}$$

All the variables are in $\mathbb{N}_{>0}$

I need to find a tight upper bound for $x$ using $m,\lambda$.

In the case of $\lambda = 1$ we can use the binomial theorem to show $x \leq m$. However for $\lambda>1$ I have no idea how to find a tight upper bound for this.

It can be shown that: $$2^x \leq \sum_{i=0}^m{{x \choose i}\lambda^i} \leq \left(\frac{\lambda e x}{m}\right)^m$$

And then we can use the solution from here: Upper bound $2^x \leq (ax)^c$

But I need a tighter bound than this. Is there any way to bound $x$ directly from this partial binomial theorem sum?

I thought of maybe doing something like this:

$$2^x = (1 + \lambda)^{x\log_{1 + \lambda}(2)}=(1 + \lambda)^{\frac{x}{\log_2(1 + \lambda)}}=\\ \sum_{i=0}^{{\frac{x}{\log_2(1 + \lambda)}}}{{{\frac{x}{\log_2(1 + \lambda)}} \choose i}\lambda^i} \leq \sum_{i=0}^m{{x \choose i}\lambda^i}$$

But I'm not sure how to continue from here (or if it even helps).

  • $\begingroup$ I suppose that you face an hypergeometric function for the rhs. $\endgroup$ – Claude Leibovici May 16 '20 at 15:33
  • $\begingroup$ @ClaudeLeibovici I'm not sure what that means, or how can I find an upper bound for x with that. $\endgroup$ – Tomer Wolberg May 16 '20 at 15:50
  • $\begingroup$ You could start with a simple upper bound of $m(x\lambda)^m$ for the RHS. $\endgroup$ – Aravind May 16 '20 at 15:59
  • $\begingroup$ @Aravind but I need to find an upper bound for $x$ not for the sum. $\endgroup$ – Tomer Wolberg May 16 '20 at 16:05
  • $\begingroup$ @Aravind what does rhs mean? $\endgroup$ – Tomer Wolberg May 16 '20 at 16:08

This is more of a long comment than an answer, but I don't get the same upper bound that you get in the $\lambda \leq 1$ case.

Assuming that $\lambda$ (and hence everything) is positive, it seems to me that:

$$\sum_{i=0}^m{{x \choose i}\lambda^i} \leq \sum_{i=0}^x{{x \choose i}\lambda^i} $$

with equality if and only if $m \geq x$.

But the right hand side of this new inequality equals $(1 + \lambda)^x$, by the binomial theorem.

So substituting this back into the original inequality we obtain:

$$2^x \leq (1 + \lambda)^x$$

When $\lambda > 1$ we get this inequality for free and so we don't learn anything new about $x$, which is similar to the problem you experienced.

When $\lambda = 1$ we have equality in the last inequality I typed, which means that we also need equality in the first equality I typed which impies $x \leq m$ as you also found.

But if $\lambda < 1$ then this inequality puts a rather strong restriction on $x$, namely:

$$x = 0$$

For any $x > 0$ the above inequality with $\lambda < 1$ is violated.

  • 1
    $\begingroup$ Yes, you're right. In the case it's smaller than 1 then x=0. But I'm more interested in the case it's bigger than 1. In my specific algorithm $\lambda$ is some integer constant that is bigger than 2. $\endgroup$ – Tomer Wolberg May 16 '20 at 22:06

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.