# Sum of 2^k less than r

1. May 14, 2013

### 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)}.$$

Last edited: May 14, 2013