Exercises 20.6 Exercises
We start with some exercises testing understanding of Landau notation.
1.
Show that \(\sigma(n)\) is \(O(n^2)\) (compare to the sum of all integers up to \(n\)).
2.
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\text{.}\) (This can be loosey-goosey.)
3.
Show that if \(g\) and \(h\) are both \(O(f)\) for some \(f\text{,}\) then \(g+h\) is also \(O(f)\text{.}\)
4.
Show that if \(g\) is \(O(f)\) for some \(f\text{,}\) then if \(b>0\) we have that \(g\) is \(O(bf)\) and \(bg\) is \(O(f)\text{.}\)
5.
Show that if \(g\) is \(O(f)\) for some \(f\) and if \(f(x)\leq h(x)\) for \(x\) large enough, then \(g\) is also \(O(h)\text{.}\)
6.
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\) (recall Definition 19.2.9).
7.
As suggested at the end of Subsection 20.2.1, if you are familiar with semilog and log-log plots and how to use them to find possible formulas, look up how to use them in Sage and modify the examples to explore whether the average value of \(\tau\) could be a power function, exponential, or something else.
8.
At the start of Subsection 20.2.1 we plot the cumulative average value of \(\tau\text{.}\) Note that because
this value is the same for \(n=4,5\text{.}\) Is there ever an \(n>5\) where this happens again?
9.
Finish off all calculus details in the argument in Subsection 20.2.3.
10.
Finish the details of the proof that \(\tau\) is \(O(\sqrt[3]{x})\)
11.
Show that \(\tau(n)\) is not \(O(1)\text{.}\) (Hint: that means there is no constant \(C\) such that \(\tau(n)\leq C\) always.)
12.
Suppose that for an arithmetic function \(f\) it is known that \(\frac{1}{n}\sum_{k=1}^n f(k)=O(1)\text{;}\) why is it still possible that \(f(n)\) is not \(O(1)\text{?}\)
13.
Show that \(\tau(n)\) is not \(O(\log(n))\text{,}\) even though it is known that \(\frac{1}{n}\sum_{k=1}^n \tau(k)=O(\log(n))\text{.}\) (Hint: look at numbers of the form \(6^k\text{,}\) and compare \(\tau\) of these to any given multiple of the natural logarithm using calculus.)
14.
Finish all calculus details of the proof of \(\sigma\)'s average size in Section 20.4.
15.
Finish the details of the first computation of Big Oh in Subsection 20.4.2.
16.
Find absolute bounds for \(\phi(n)\) (simple polynomial or log formulas in terms of \(n\)).
17.
Use data, graphs, whatever to conjecture what type of growth the average value of \(\phi\) has up to \(n\text{.}\) Is it logarithmic, linear, quadratic, exponential, something else? Bonus if you find a coefficient for the growth!