Given $\{a_n\}$ is non decreasing, non negative and $$a_{m\cdot n} \leq a_m + a_n,$$ show that there exists $C$ such that $a_n \leq C \log(n)$ for $n\geq 2$.

First taking $n=2^k$, we see that $$a_{2^k} \leq k a_2 . $$ We claim that $$C \log(2^k) = ka_2 \quad \Longrightarrow \quad C = \frac{a_2}{\log(2)}.$$ Thus we need to show $$a_n \leq \frac{\log n}{\log 2} a_2 = a_2 \log_2 n.$$

By induction, when $n=2$, we have $a_2 \leq a_2 *1 $. Assume the inequality holds up to $n$, now if $n+1$ is not prime, we can rewrite $n+1 = c\cdot d$ for some $2\leq c,d\leq n$. By the induction assumption and the inequality from the problem, we have $$a_{c\cdot d} \leq a_c + a_d \leq a_2 \log_2 c + a_2 \log_2 d = a_2 \log_2 (c\cdot d).$$

But what should I do if $n+1$ is prime? Or do I need to find a better constant $C$?

Thank you very much!

Edit: I see there is a problem with my $C$, taking $$a_2 =1 \quad a_3 = 2 \quad a_4 = 2,$$ the inequality will not work for $2 = a_3 \not\leq \log_2 3$.

  • 2
    $\begingroup$ Well, by the givens, $a_n \leq a_{n+1} \leq a_{n+2}$, so shifting your bound to the left by one will provide a bound for all integer indices, even the prime ones. $\endgroup$ Commented Jul 9, 2014 at 14:22

1 Answer 1


If $(k-1)<\log_2n\le k$, i.e. $2^{k-1}< n\le 2^k$, then $a_{2^{k-1}}\le a_n\le a_{2^k}\le ka_2$ (by nondecreasing and your result). We conclude that $$ a_n\le a_2\cdot \lceil \log_2 n\rceil \le a_2(\log_2n+1)\le 2a_2\log_2n$$ where the last step uses $\log_2 n\ge1$ (from $n\ge 2$) and $a_2\ge 0$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .