Claim: For any positive integer $k$, if $\sum_{p=1}^k \frac{1}{\sqrt{p}} \ge 2\sqrt{k+1} - 2$, then $\sum_{p=1}^{k+1} \frac{1}{\sqrt{p}} \ge 2\sqrt{k+2} - 2$.
Hint: notice that $(\sqrt{x+1} - \sqrt{x+2}\ )^2 \ge 0$. What does this imply about $2\sqrt{x+1}\sqrt{x+2}$?
This looks a lot like the inductive step of an induction proof. So let's try breaking down the larger summation and using the given fact about the smaller summation. That gives us this:
$\sum_{p=1}^{k+1} \frac{1}{\sqrt{p}} = \frac{1}{\sqrt{k+1}} + \sum_{p=1}^k \frac{1}{\sqrt{p}} \ \ge \ \frac{1}{\sqrt{k+1}} + 2\sqrt{k+1} - 2$
To get to the conclusion of our claim, we need to show that $\frac{1}{\sqrt{k+1}} + 2\sqrt{k+1} - 2 \ge 2\sqrt{k+2} - 2$.
Let's remove that annoying $-2$ on both sides: $\frac{1}{\sqrt{k+1}} + 2\sqrt{k+1} \ge 2\sqrt{k+2}$.
Now add the two items on the lefthand side:
$\frac{1}{\sqrt{k+1}} + 2\sqrt{k+1} = \frac{1}{\sqrt{k+1}} + \frac{2(k+1)}{\sqrt{k+1}} = \frac{1 + 2(k+1)}{\sqrt{k+1}} = \frac{2k + 3}{\sqrt{k+1}}$
So we need to show that $\frac{2k + 3}{\sqrt{k+1}} \ge 2\sqrt{k+2} $.
Multiply by $\sqrt{k+1}$ gives us $2k + 3 \ge 2\sqrt{k+2}\sqrt{k+1} $ that we need to somehow prove.
>>>And now a miracle happens <<<
Maybe the hint will be helpful?
$(\sqrt{k+1} - \sqrt{k+2}\ )^2 \ge 0$
Multiplying this out gives us $(k+1) - 2\sqrt{k+1}\sqrt{k+2} + (k + 2) \ge 0$.
If move the square root term to the other side and simplify the rest, we get $2k + 3 \ge 2\sqrt{k+1}\sqrt{k+2}$. That's the missing link in our proof, so let's write it up nicely.
Lemma: For any positive integer $k$, $2k + 3 \ge 2\sqrt{k+1}\sqrt{k+2}$.
Proof of lemma: Let $k$ be a positive integer.
Notice that $(\sqrt{k+1} - \sqrt{k+2}\ )^2 \ge 0$ because it's the square of a real number.
Multiplying this out gives us $(k+1) - 2\sqrt{k+1}\sqrt{k+2} + (k + 2) \ge 0$.
Simplifying gives us $(2k+3) - 2\sqrt{k+1}\sqrt{k+2} \ge 0$.
This implies that $2k + 3 \ge 2\sqrt{k+1}\sqrt{k+2}$.
Claim: For any positive integer $k$, if $\sum_{p=1}^k \frac{1}{\sqrt{p}} \ge 2\sqrt{k+1} - 2$, then $\sum_{p=1}^{k+1} \frac{1}{\sqrt{p}} \ge 2\sqrt{k+2} - 2$,
Proof: Let $k$ be a positive integer and suppose that $\sum_{p=1}^k \frac{1}{\sqrt{p}} \ge 2\sqrt{k+1} - 2$.
So then
\begin{eqnarray*} \sum_{p=1}^{k+1} \frac{1}{\sqrt{p}} &=& \frac{1}{\sqrt{k+1}} + \sum_{p=1}^k \frac{1}{\sqrt{p}} \ \ge \ \frac{1}{\sqrt{k+1}} + 2\sqrt{k+1} - 2 \\ &=& \frac{1}{\sqrt{k+1}} + \frac{2(k+1)}{\sqrt{k+1}} - 2 = \frac{1 + 2(k+1)}{\sqrt{k+1}} - 2 = \frac{2k + 3}{\sqrt{k+1}} - 2 \end{eqnarray*}
So we have $\sum_{p=1}^{k+1} \frac{1}{\sqrt{p}} \ge \frac{2k + 3}{\sqrt{k+1}} - 2 $ (Equation 1)
From the lemma, we know that $2k + 3 \ge 2\sqrt{k+1}\sqrt{k+2}$. So
\begin{eqnarray*} \frac{2k + 3}{\sqrt{k+1}} - 2 &\ge& \frac{2\sqrt{k+1}\sqrt{k+2}}{\sqrt{k+1}} - 2 = 2\sqrt{k+2} - 2 \end{eqnarray*}
Combining this with Equation 1 gives us $\sum_{p=1}^{k+1} \frac{1}{\sqrt{p}} \ge 2\sqrt{k+2} - 2$, which is what we needed to show.
Suppose that $f$ and $g$ are functions and $f(x)$ is $O(g(x))$. Does this mean that $\log (f(x))$ is $O(\log(g(x)))$?
What if output values of $f$ or $g$ are less than one. In that case the log of those values would be less than one so they would not be able to be covered by a big-O releation since big-O requires that the domain be positive at least after some value $k$. We can address this by requiring that $f$ and $g$ have output values that are $>1$.
So another possible issue is that if both functions are decreasing that the constant factor might start to dominate. To avoid this we can assert that both $f$ and $g$ are increasing functions.
Now we have the following $f$ and $g$ are increasing functions from the reals to the reals, for which all output values are $>1$. If $f(x)$ is $O(g(x))$ then $\log (f(x))$ is $O(\log(g(x)))$
Exam questions sometimes ask for short justifications. In this case, we might say the following. Suppose that $f(x)$ is $O(g(x))$. Then there are positive reals $c$ and $k$ such that $f(x) \le cg(x)$ for all $x \ge k$. Then $\log(f(x)) \le \log c + \log(g(x))$ for all $x \ge k$. Since $\log c$ is a constant, we can find a multiplier $K$ such that $\log(f(x)) \le K\log(g(x))$.
Suppose $f$ and $g$ are functions from the reals ot the reals and $f$ and $g$ are increasing functions, for which all output values are $>1$ and $f(x)$ is $O(g(x))$.
Since $f(x)$ is $O(g(x))$ there are there are positive reals $c$ and $k$ such that $f(x) \le cg(x)$ for all $x \ge k$.
Since we know that $f$ and $g$ are always $>1$ we can take the log of both sides giving use the following for all $x \ge k$.
\begin{eqnarray*} \log(f(x)) &\le& \log(g(cx)) \\ \log(f(x)) &\le& \log c + \log(g(x)) \end{eqnarray*}
We need to find some value $C_{log}$ that we can multiply $\log(g(x))$ by such that it is $\ge \log c + \log(g(x))$ for all $x \ge k$. Since we know that $g$ is increasing and $>1$ we now that $log(g(k)) \le \log(g(x))$ for all $x \ge k$. So we can solve for $C_{log}$ at $k$ and know it will work for all values of $x \ge k$.
\begin{eqnarray*} \log c + \log(g(k)) &=& C_{log} \cdot \log(g(k)) \\ C_{log} &=& \frac{\log c + \log(g(k))}{\log(g(k))} \end{eqnarray*}
Now we have $ \log(f(x)) \le \log c + \log(g(x)) \le C_{log} \cdot \log(g(x))$ for all $x \ge k$ which is what we needed to show.
You may well be convinced at this point. However, you might be worried by the fact that the above proof jumps from $\log c + \log(g(k)) = C_{log} \cdot \log(g(k))$ to a similar equation for all $x \ge k$. If this seems obvious, just skip ahead. If this bothers you, here's how to show this is true algebraically.
We know that $\log c + \log(g(k)) = C_{log} \cdot \log(g(k))$. So $\log c = C_{log} \cdot \log(g(k)) - \log(g(k)) = (C_{log} -1)\cdot \log(g(k))$
Since $g$ is monotonically increasing, we know that $\log(g(x)) \ge \log(g(k))$ for all $x \ge k$.
So $\log c = (C_{log} -1)\cdot \log(g(k)) \le (C_{log} -1)\cdot \log(g(x))$ for all $x \ge k$.
So, $\log c \le C_{log}\cdot \log(g(x)) -\log(g(x))$ for all $x \ge k$,
And so $\log c + \log(g(x)) \le C_{log} \cdot \log(g(x))$ for all $x \ge k$,
Consider functions $f(n)$ and $g(n)$ where $f$ is $O(n^2)$ and $g$ is $O(2^n)$. Is $f(n)$ big-O of $g(n)$?
While at first glance it might seem so consider the following $f(x) = n^2$ and $g(x)=1$. It is clear to see that $f$ is $O(n^2)$ and $g$ is $O(2^n)$ but it is also clear that $f(x)$ is not $O(g(x))$.