We're supposed to give two solutions, one using an integral and one without an integral. My solution using an integral is the following:
$\int_0^n \frac{1}{i} dx \leq \sum_{i=1}^n \frac{1}{i} \leq \int_1^{n+1} \frac{1}{i} dx$
$\implies \sum_{i=1}^n \frac{1}{i} = \Theta(\ln(n)) $ (Is this that obvious that i don't need proof? I don't quite understand this one myself, it was given as a logical result of the integral criterium in our book.)
$\ln(n) < n$ for positive n.
We substitute $n$ with $\sqrt{n^2}$:
$\ln(\sqrt{n^2}) < \sqrt{n^2}$
$2\cdot \ln(\sqrt{n}) < 2\cdot \sqrt{n}$
$\implies \ln(n) = \mathcal{O}(\sqrt{n})$
And therefore our sum is $\mathcal{O}(\sqrt{n})$ as well.
Is this solution correct? I only used the integral to conclude that we could also just show $\ln(n) = \mathcal{O}(\sqrt{n})$.
Would this count as the solution using an integral? How would the solution without an integral look like?
For a solutoin without integral, note that for $n\in\Bbb N$, $$\sqrt{n}-\sqrt{ n-1}=\frac1{\sqrt{n}+\sqrt {n-1}}\ge \frac1{2\sqrt {n}}.$$ Then by telescoping $$ 2\sqrt n-2\sqrt 0\ge \sum_{i=1}^n\frac1{\sqrt i}\ge \sum_{i=1}^n\frac1{ i}.$$