3
$\begingroup$

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

$\endgroup$
  • 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$ – Eric Towers Jul 9 '14 at 14:22
3
$\begingroup$

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

$\endgroup$

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.