# Prove that the sum is always greater than $1$

Prove that $\frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}+...+ \frac{1}{n^2} \ge 1$, for all natural numbers $n$. I tried to use mathematical inducion but failed and I tried to figure out a short formula for the sum but I couldnt find any.

• The smallest is $\frac{1}{n^2}$, and there should be $n^2$ terms – HeatTheIce Feb 9 '15 at 20:52
• Ah, almost $n^2$, so this estimate is close to $1$ but not good enough. We need a better approach. – Orest Bucicovschi Feb 9 '15 at 20:54
• If we were able to use logarithms then it is easier. – Orest Bucicovschi Feb 9 '15 at 20:55
• One approach: the whole sum from $1$ to $n^2$ is about $C + \log(n^2)$, while the sum from $1$ to $n$ is about $C + \log n$. So in fact this sum is about $\log n$, growing slowly to $\infty$. – Orest Bucicovschi Feb 9 '15 at 20:56
• There are in fact $n^2 - n + 1$... so this estimate is a bit too rough... – Orest Bucicovschi Feb 9 '15 at 20:57

Without integrals. If $n\ge4$ $$\sum_{k=n}^{n^2}\frac1k>\sum_{k=n}^{2n-1}\frac1k+\sum_{k=2n}^{3n-1}\frac1k+\sum_{k=3n}^{4n-1}\frac1k>n\,\frac{1}{2\,n}+n\,\frac{1}{3\,n}+n\,\frac{1}{4\,n}=\frac12+\frac13+\frac14=\frac{14}{12}.$$

• I like this solution. The sum is so much larger than 1 in general. You can throw out most of it. – Joel Feb 9 '15 at 21:02
• Just one little thing: its $\frac{13}{12}$, not $14$. – HeatTheIce Feb 9 '15 at 21:31
• Yep, over $1$ by $\frac{1}{3}- \frac{1}{4}$ – Orest Bucicovschi Feb 9 '15 at 21:33

$$\sum_{k=n}^{n^2} \frac{1}{k} = \frac{1}{n} + \sum_{k=n+1}^{n^2} \frac{1}{k} \ge \frac{1}{n} + \frac{n^2-(n+1)+1}{n^2} = 1.$$ The final fraction due to there being $n^2-(n+1)+1$ terms, each of which is at least $\frac{1}{n^2}$.

Using some calculus you can see that $$\sum_{k=n}^{n^2} \frac{1}{k} \ge \int_{n}^{n^2} \frac{1}{x} dx = \ln(n^2) - \ln(n) = \ln(n).$$

Certainly this is larger than 1 for $n\ge 3$. For $n=1$ the claim follows automatically. For $n=2$ we check $$\frac12 + \frac13 + \frac14 = \frac{6+4+3}{12} = \frac{13}{12}.$$

Since we know this holds for $n=2$, another approach is to show that $f(n)=\sum_{k=n}^{n^2}1/k$ is an increasing function. Since between $f(n)$ and $f(n+1)$ we lose $1/n$ and gain $$\frac{1}{n^2+1} + \frac{1}{n^2+2} + \cdots + \frac{1}{(n+1)^2}$$ we need to show that the sum of the new terms is larger than $1/n$.

We can get a lower bound on this tail: $$\frac{1}{n^2+1} + \frac{1}{n^2+2} + \cdots + \frac{1}{(n+1)^2} > \frac{2n+1}{(n+1)^2}.$$ If this left term is larger than $1/n$ we win. Using some precalculus type reasoning we can see that $$\frac{2n+1}{(n+1)^2} \ge \frac1n$$ is equivalent to $$n^2 - n - 1 \ge 0.$$

This is satisfied for $n \ge 2$.

• +1, using the integral is the approach that can give the asymptotic expansion. – Orest Bucicovschi Feb 9 '15 at 21:10
• I believe if you take the error bounds seriously enough, you can show that the sum is actually $\log(n)+O(1)$. – Joel Feb 9 '15 at 21:24
• Or even $O(1/n)$ now that I think about it. – Joel Feb 9 '15 at 21:25
• Oh, it seems to be about Harmonic numbers en.wikipedia.org/wiki/Harmonic_number – Orest Bucicovschi Feb 9 '15 at 21:31

Just another way, using Cauchy-Schwarz inequality: $$\frac1{n+k}+\frac1{n^2-k} \ge \frac4{n^2+n}$$

$$\implies 2\sum_{k=0}^{n^2-n}\frac1{n+k} \ge \frac4{n^2+n}(n^2-n+1)$$

So all we need to show is $2(n^2-n+1) \ge n^2+n \iff (n-1)(n-2)\ge 0$ which is evidently true for integer $n$.

Using the Arithmetic-Harmonic Inequality: $$\frac{n^2-n+1}{n+(n+1)+\cdots+n^2}\leq\frac{1}{n^2-n+1}\left(\frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{n^2}\right)$$

Now, the denominator of the left-hand fraction is: $$\sum_{k=0}^{n^2-n}(n+k)=\sum_{k=1}^{n^2-n+1}(n+k-1)=\sum_{k=1}^{n^2-n+1}(n-1)+\sum_{k=1}^{n^2-n+1}k=\frac{n^4+n}{2}$$

Hence, we have that $$1\leq\frac{2(n^2-n+1)}{n(n+1)}=\frac{2(n^2-n+1)^2}{n(n+1)(n^2-n+1)}=\frac{2(n^2-n+1)^2}{n^4+n}\leq\frac{1}{n}+\cdots+\frac{1}{n^2}$$

We can recover the first inequality here from the fact that $0\leq (n-1)(n-2)$ for all $n\geq 1$.

• Check the number of terms! There are $n^2-n+1 \neq n^2+1$ terms. Still can be made to work after correcting that. – Macavity Feb 10 '15 at 6:43
• @Macavity thanks for the correction. Fixed – Robert Wolfe Feb 10 '15 at 6:57