(a) Let and be functions from the set of positive integers to the set of real numbers. State the definition of the fact that is .
We say that is if there exists a pair of positive constants such that, for all , we have .
(b) Use your definition from (a) to prove that is . Show all your work.
We want to find a pair of positive constants such that, for all , we have .
Assume that . Then we have inequalities.
When we add up the left sides of these inequalities, we get .
Adding up the right sides of these inequalities, we get .
There are exactly terms in this expression, so which is equal to .
This shows that whenever .
We also have that , so this gives us that
In particular, we have that whenever .
This proves that is , with witnesses .