$\sum_{i=1}^n 1/i \leq c\log n$ This is what I want to show: $\sum_{i=0}^n 1/i \leq c \log n$ for all $n>N$
My current approach was this:
$\sum_{i=1}^n 1/i
= ( \int \sum_{i=1}^n 1/i )'
= ( \sum_{i=1}^n \int 1/i )'
= ( \sum_{i=1}^n \log i )'
\leq ( \sum_{i=1}^n \log n )'
= ( n  \log n )'
= 1 + \log n 
\leq c  \log n \Leftrightarrow c > 1$
But I was told this was incorrect, because I could not swap the integral and the sum in line 3 (different variables).
Do you have any suggestion to turn this in a valid proof?
 A: Consider the function $ f(x) = \frac{1}{x} $, then it's decreasing in $(0, + \infty )$ so considering the area under the integral we have $$\sum_{i = 2}^{n}\frac{1}{i} \leq \int_{1}^{n} \frac{1}{x} dx = \log n$$ and so $$\sum_{i = 1}^{n}\frac{1}{i} \leq \log n + 1 \leq c \log n$$ for all $n > N$
A: I'm not sure what you mean by ' in this context.
An easy bounding technique is by considering left and right Riemann sums (due to monotonicity, but essentially just upper and lower bounding on intervals of the form $[i-1,i]$ for $i \in \mathbb{N}$) as in this link.
Essentially, if you consider bars of height $1/i$ on $[i-1,i]$ for $i=1,2,\ldots$, the area under the first $n$ bars (i.e. integrate the fn determined by these bars) is precisely the $n$-th harmonic number ($H_n=\sum_{k=1}^n \frac{1}{k}$). Note that $f(x)=1/x$ is an upper bound, $f(x)=1/(x+1)$ is a lower bound on the height of those bars. Thus, integrate $f(x)$ for an upper bound (from $x=1$ to $n$, and bound the first bar by 1), $f(x)=1/(x+1)$ for a lower bound (from $x=0$ to $n$).
This gives the bounds
$$H_n \leq 1 + \log n$$
$$H_n \geq \log(n+1)$$
Now, find a constant for the upper bound as before (I have shown something a bit better - that $H_n \approx \log(n)$ in some precise sense).
