0
$\begingroup$

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.

Additional question:-

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

$\endgroup$
0
$\begingroup$

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.

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

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.