- Show that \(\sigma(n)\) is \(O(n^2)\) (compare to the sum of all integers).
- Use the formula for the sum of the first \(n\) perfect squares (often encountered in a Transition to Proof course or when first doing definite integrals in Calculus) and the previous exercise to show that the average value of \(\sigma(n)\) is Big Oh of \(n^2\). (This can be loosey-goosey.)
- Find a formula for the average value of the \(u\) and \(N\) functions (up through \(n\)), where \(u(n)=1\) for all \(n\) and \(N(n)=n\) for all \(n\).
- Finish the details of the proof that \(\tau\) is \(O(\sqrt[3]{x})\)
- Show that \(\tau(n)\) is not \(O(1)\). (Hint: that means there is no constant \(C\) such that \(\tau(n)\leq C\) always.)
- Why would it not contradict our theorem above that \(\frac{1}{n}\sum_{k=1}^n\tau(k)=O(\ln(n))\) to say that \(\tau(n)\) is not \(O(\ln(n))\)?
- Show that \(\tau(n)\) is not \(O(\ln(n))\). (Hint: look at numbers of the form \(6^k\), and compare \(\tau\) of these to any given multiple of the natural logarithm using calculus.)
- Find absolute bounds for \(\phi(n)\) (simple polynomial or log formulas in terms of \(n\)).
- Use data, graphs, whatever to conjecture what type of growth the average value of \(\phi\) has up to \(n\). Is it logarithmic, linear, quadratic, exponential, something else? Bonus if you find a coefficient for the growth!
