# If $f(2^{2^{k+1}})<c*f(2^{2^{k}})$ for some constant $c$, can we say that $f(x)=O( \log \log x)$

If it helps you can assume that $f$ is a sub additive function, although it probably might be implied from the conditions. Also $f$ is over positive integers.

What can be said about the following sum

$$\log n \sum_{k=0}^{\log \log n} \frac{1}{{2^{k}}} f\left( 2^{2^{k}}\right)$$

Obviously, from the given inequality we gain

$$f( 2^{2^k}) < ck f(2).$$

Then, let $x \in \mathbb N$. There exists a unique $k = k(x)$ such that $x \in [2^{2^k}, 2^{2^{k+1}})$. Then

$$f(x) \le f(2^{2^k}) + f(x - 2^{2^k}).$$

From this we see by induction that $f(x) \le f(2^{2^{k+1}}) < c(k+1) f(2)$. But

$$k(x) = \lfloor \log_2(\log_2(x)) \rfloor,$$

proving the first claim. The given sum will be bounded by

$$\log(n) \sum_{k=0}^{\log(\log(n))} \frac{c(k+1)}{2^k} f(2)$$

by the above estimates. One can consider the polynomial $$p_n(x) := 4 \log(n) \sum_{k=0}^{\log(\log(n))} cx^k f(2)$$

and observe that the sum comes from a derivative of that polynomial, inserting $x = 1/2$. Then one should be able to apply calculus to get some further bounds.

• In the very first equation did you mean $c^k$ instead of ck? – Vk1 Jul 16 '18 at 10:30
• Unfortunately, my computer does not display your comment right, so I don't know. – AlgebraicsAnonymous Jul 16 '18 at 17:17