Finite harmonic sum inequality I wish to prove some inequality involving a finite harmonic series: 
$$\sum_{k=n+1}^{n^2}\frac{1}{k}>\sum_{k=2}^{n}\frac{1}{k}$$
Certainly $\frac{1}{nk+q}≥\frac{1}{n(k+1)}$
for $q=1,2,3,....,n.$
So that $$\sum_{q=1}^n\frac{1}{nk+q}≥\frac{1}{k+1}$$
Adding the last inequality from $k=1$ to $n-1$  should yield the required inequality but I don't see how it does.
 A: You want to prove that
$$ H_{n^2}-H_{n} \geq H_n -1 $$
i.e. that 
$$ H_{n^2}-2H_n\geq -1. $$
On the interval $\left[\frac{1}{2},1\right]$ we have $\frac{x-\log(1+x)}{x^2}\in\left[0.3,0.4\right]$, so
$$ \frac{3}{25}\leq\sum_{k=2}^{n}\frac{1}{k}-\sum_{k=2}^{n}\log\left(1+\frac{1}{k}\right)\leq\frac{2}{5}\sum_{k=2}^{n}\frac{1}{k^2}\leq \frac{2}{5}(\zeta(2)-1)\leq\frac{7}{25} $$
where $\sum_{k=2}^{n}\log\left(1+\frac{1}{k}\right) = \log(n+1)-\log(2).$ It follows that
$$ H_{n^2}-2H_n \geq \log(n^2+1)+\frac{3}{25}-2\log(n+1)-\frac{14}{25}\geq\log\frac{n^2+1}{(n+1)^2}-\frac{12}{25}\geq -1 $$
for any $n\geq 3$, and the other cases can be easily checked by hand.
A: Let $H_n=\sum_{k=1}^n \frac1k$. Then we want to prove $H_{n^2}-H_n\geq H_n-1$, which is equivalent to $$H_{n^2}\geq 2H_n-1.$$
Indeed, using $\ln(n)+\gamma\le H_n\le \ln(n)+\gamma+\frac1{2n}$ (it is a weaker version of equation (8)), we get $$H_{n^2}\geq \ln(n^2)+\gamma=2\ln(n)+\gamma$$ and $$2H_n -1\le \frac1n+2\gamma +2\ln(n)-1$$ so it remains to prove that $$\frac1n+\gamma\le1,$$ which is indeed true for $n\geq 3$ (note that $\gamma\approx0.57$ is the Euler-Mascheroni constant). The cases $n=1,2$ can be checked manually.
