For each intger $k \geq 1 $, determine the average order of $\sigma_k(n)$

66 Views Asked by At

For each intger $k \geq 1 $, determine the average order of $\sigma_k(n)$

We have that $\sigma_k(n)= \sum_{d|n} d^k= \sum_{uv=a} v^k$ It follows that we have $$\sum_{a\leq n}\sigma_k(n)= \sum_{a\leq n} \sum_{uv=a} v^k=\sum_{u=1}^{n} \sum_{v=1}^{\lfloor \frac{n}{u} \rfloor} v^k= \frac{1}{1+k}\sum_{u=1}^{n} \lfloor \frac {n}{u}\rfloor ((\lfloor \frac {n}{u}\rfloor)^k +1 ) = \frac{1}{1+k}\sum_{u=1}^{n} (( \frac {n}{u}) +O(1) )^{k+1} $$

$$\sum_{u=1}^{n} (( \frac {n}{u}) +O(1) )^{k+1}=\sum_{u=1}^{n} (\frac{n^{k+1}}{u^{k+1}} + \frac{n^{k}}{u^{k}} O(1) + \cdots )=\sum_{u=1}^{n} \frac{n^{k+1}}{u^{k+1}} + O(n^k \sum_{u=1}^{n} \frac{1}{u^k}) $$ There are some additional O terms but they are all lesser than the one listed so we don't care about them.

$$n^{k+1}\sum_{u=1}^{n} \frac{1}{u^{k+1}} = \frac {n^{k+1}}{k+1} (\zeta(k+1) - \sum_{u=n+1}^{\infty} \frac{1}{u^{k+1} })= \frac {n^{k+1}}{k+1} \zeta(k+1) - n^{k+1} O(\frac {1}{n^k}) = \frac {n^{k+1}}{k+1} \zeta(k+1) - O(n) $$

For the error terms we have that.

$ O(n^k \sum_{u=1}^{n} \frac{1}{u^k})$ we notice that as $ n\to \infty$ that $\sum_{u=1}^{n}\frac{1}{u^k} \to \zeta (k)$ for all $k >1 $ which is a constant so we have that $ O(n^k \sum_{u=1}^{n} \frac{1}{u^k}) = O(n^k) $ for all $ k >1 $

Except for the value when $k =1$ in this case we get that $ O(n \sum_{u=1}^{n} \frac{1}{u})$ which is $O(n \log (n) )$ instead so the largest error term appears to be $O(n \log (n) )$ when $k=1$ and is $ O(n^k \sum_{u=1}^{n} \frac{1}{u^k}) = O(n^k) $ for all $ k >1 $ it follows that we have the average order is $\frac {n^{k+1}}{k+1} \zeta(k+1) + O(n^k)$ for all $k>1$ and the average order when $k=1$ is $\frac {n^{2}}{2} \zeta(k+1) + O(n \log (n) )$ when k =1.