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