Theorem

Suppose $H:\mathbb{N}^+ \to [0,\infty)$ is a function satisfying Then $H(n) = H(2) \lg n$.

Proof

Define $F(n) = H(n) - H(2) \lg n$. Notice that

Let $\epsilon$ be given. Ask for a $2^M$ such that $$|F(n+1) - F(n)| < \epsilon/2$$ for all $n \ge 2^M$. Define $$\mu_k = \max_{2^k \le n \lt 2^{k+1}} | F(n)|$$ Let $k$ abbreviate $\lfloor \lg n \rfloor$. Suppose $n \ge 2^{\max(M, 2\mu_M/\epsilon)}$. Because $k \ge M$, we have $\mu_{k+1} \le \mu_k + \epsilon/2$, (think about how $F(2n)=F(n)$ constrains one $\mu_k$ to be close to the next) and therefore $\mu_k \le \mu_M + k\epsilon/2$. With this and the fact that $k \ge 2\mu_M/\epsilon$, we can derive $${ |F(n)|\over \lg n } \le {\mu_k \over k} \le {\mu_M \over k} + {\epsilon\over 2}\le {\epsilon\over 2}+{\epsilon\over 2} = \epsilon$$ Since $\epsilon$ was arbitrary, we've shown $$\lim_{n\to \infty}{ F(n)\over \lg n } = 0$$ and so for every $m$ we have $$0 = \lim_{n\to \infty}{ F(m^n)\over \lg m^n } = \lim_{n\to \infty}{ n F(m)\over n \lg m } = { F(m)\over \lg m } $$ and $F(n)$ is therefore identically zero, QED.