3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The smallest is $\frac{1}{n^2}$, and there should be $n^2$ terms $\endgroup$ – HeatTheIce Feb 9 '15 at 20:52
  • $\begingroup$ Ah, almost $n^2$, so this estimate is close to $1$ but not good enough. We need a better approach. $\endgroup$ – Orest Bucicovschi Feb 9 '15 at 20:54
  • $\begingroup$ If we were able to use logarithms then it is easier. $\endgroup$ – Orest Bucicovschi Feb 9 '15 at 20:55
  • 1
    $\begingroup$ 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$. $\endgroup$ – Orest Bucicovschi Feb 9 '15 at 20:56
  • 1
    $\begingroup$ There are in fact $n^2 - n + 1$... so this estimate is a bit too rough... $\endgroup$ – Orest Bucicovschi Feb 9 '15 at 20:57
11
$\begingroup$

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}. $$

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

$$ \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}$.

$\endgroup$
2
$\begingroup$

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$.

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

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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Macavity Feb 10 '15 at 6:43
  • $\begingroup$ @Macavity thanks for the correction. Fixed $\endgroup$ – Robert Wolfe Feb 10 '15 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.