Lower Bound for Sum of 2^k Less Than r

[jostpuur]

Assume $n\in\mathbb{N}$ and $r\in\mathbb{R}$ are some fixed constants and $r>0$. I want to find some nice lower bound for the amount of elements $(k_1,k_2,\ldots,k_n)\in\mathbb{N}^n$ such that $2^{k_1}+\cdots + 2^{k_n}\leq r$.

In other words, if we define a function

$$f:\mathbb{N}^n\to\mathbb{R},\quad f(k_1,\ldots, k_n)=2^{k_1}+\cdots + 2^{k_n}$$

I want to find some nice formula for a some reasonably large quantity $\varphi(r,n)$ such that

$$\varphi(r,n)\leq \# f^{-1}([1,r])$$

where # means the number of elements in the set.

I tried to approximate some sums as integrals, but didn't get anywhere.

The special case $n=1$ easy. The number of elements $2^0,2^1,2^2,\ldots$ which are less than $r$ is

$$\Big[\frac{\log(r)}{\log(2)}\Big]+1$$

where $x\mapsto [x]$ is the floor function defined by $[x]=j\in\mathbb{Z}$ and $j\leq x < j+1$.

So if we want $\varphi(r,1)$ "nice", it could be made differentiable by setting

$$\varphi(r,1) = \frac{\log(r)}{\log(2)}.$$

 

[jvicens]

Hello,

Thank you for sharing your problem on this forum. This is an interesting question, and I believe there are a few different approaches that could be taken to find a nice lower bound for the number of elements satisfying the given conditions.

One possible approach is to use the fact that for any fixed n, the set of all possible combinations of n elements from the set \{0,1,\ldots,n\} is equal to 2^n. This means that the number of elements satisfying the given conditions can be no more than 2^n. Therefore, a simple lower bound for \varphi(r,n) could be 2^n.

Another approach could be to use the fact that for any given k\in\mathbb{N}, the set of all elements k_i satisfying 2^{k_i}\leq k is finite. This means that for any fixed r, there exists a largest value of n for which the number of elements satisfying the given conditions is less than or equal to r. This value of n can be found by solving the equation 2^n\leq r, which gives n=\log_2(r). Therefore, a lower bound for \varphi(r,n) could be \log_2(r).

I hope these ideas are helpful in finding a nice lower bound for the number of elements satisfying the given conditions. Good luck in your research!