# Tighter upper bound on $x$ where $2^x \leq \sum_{i=0}^m{{x \choose i}\lambda^i}$

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

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

• 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. – Tomer Wolberg May 16 '20 at 22:06