Given $a_{m*n} \leq a_m + a_n$, show that there exists $C$ such that $a_n \leq C log(n)$

Question

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

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