0
$\begingroup$

Let $\{ f_{n}(x) \}$ be a sequence of piecewise linear functions of $x$. If the order of growth of $\sum_{n \leq x} f_{n}(x)$ is $O(g(x))$ for some smooth $g(x)$, then what can be said about the order of $\sum_{n \leq x} f_{n}(x) \log n$? In particular, if $\sum_{n \leq x} a_{n} = O(1)$, then is $\sum_{n \leq x} a_{n} \log n$ at most $O(\log x)$, where $a_n$ is a sequence depending only on $n$?

  • 0
    I thought the generalization was obvious--see Edit.2012-09-30

1 Answers 1

3

Let $A_n=\sum\limits_{k=1}^na_k$ and $B_n=\sum\limits_{k=1}^na_k\log k$. Abel's transform yields $B_n=A_n\log n-\sum\limits_{k=1}^{n-1}A_k\log\left(\frac{k+1}k\right). $ Assume first that $|A_n|\leqslant A$ for every $n\geqslant1$, then $ |B_n|\leqslant A\log n+\sum\limits_{k=1}^{n-1}A\log\left(\frac{k+1}k\right)=2A\log n. $ This proves that, if $A_n=O(1)$, then $B_n=O(\log n)$.

More generally, assume that $|A_n|\leqslant C_n$ for every $n\geqslant1$, where the sequence $(C_n)_n$ is positive and nondecreasing, then $|A_k|\leqslant C_n$ for every $k\leqslant n$ hence $ |B_n|\leqslant C_n\log n+\sum\limits_{k=1}^{n-1}C_n\log\left(\frac{k+1}k\right)=2C_n\log n. $ This proves that, if $A_n=O(C_n)$, then $B_n=O(C_n\log n)$.