7
$\begingroup$

$$\dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt n}\geq \sqrt n$$ I want to prove this by Induction $$n=1 \checkmark\\ n=k \to \dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt k}\geq \sqrt k\\ n=k+1 \to \dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt {k+1}}\geq \sqrt {k+1}$$ so $$\dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt k}+\dfrac{1}{\sqrt {k+1}}\geq \sqrt k+\dfrac{1}{\sqrt {k+1}}$$now we prove that $$\sqrt k+\dfrac{1}{\sqrt {k+1}} >\sqrt{k+1} \\\sqrt{k(k+1)}+1 \geq k+1 \\ k(k+1) \geq k^2 \\k+1 \geq k \checkmark$$ and the second method like below ,

and I want to know is there more Idia to show this proof ? forexample combinatorics proofs , or using integrals ,or fourier series ,....

Is there a close form for this summation ?

any help will be appreciated .

$\endgroup$
5
$\begingroup$

Combining AM-HM $$\left(a_1+a_2+...+a_n\right)\left(\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_n}\right)\geq n^2$$ Thus $$\left(\sqrt{1}+\sqrt{2}+...+\sqrt{n}\right)\left(\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}}\right)\geq n^2$$ and $$n\sqrt{n}\geq\left(\sqrt{1}+\sqrt{2}+...+\sqrt{n}\right)$$ so $$n\sqrt{n}\left(\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}}\right)\geq n^2$$ and $$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}}\geq \sqrt{n}$$

$\endgroup$
  • $\begingroup$ That's kind of perverse to use $\sqrt k\le\sqrt n$ to get $n\sqrt n$ and not use it for $\frac{1}{\sqrt k}\ge\frac{1}{\sqrt n}$ as in Khosrotash solution. $\endgroup$ – zwim Feb 20 '17 at 0:21
  • $\begingroup$ @zwim as long as it works $\endgroup$ – rtybase Feb 20 '17 at 0:29
26
$\begingroup$

$$\begin{cases}\dfrac{1}{\sqrt 1}\geq \dfrac{1}{\sqrt n}\\+\dfrac{1}{\sqrt 2}\geq \dfrac{1}{\sqrt n}\\+\dfrac{1}{\sqrt 3}\geq \dfrac{1}{\sqrt n}\\ \vdots\\+\dfrac{1}{\sqrt n}\geq \dfrac{1}{\sqrt n}\end{cases} \\\\$$

sum of left hands is $\underbrace{\dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt n}}$ sum of the right hands is $n\times \dfrac{1}{\sqrt n}$ so $$\dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt n} \geq n\dfrac{1}{\sqrt n}=\dfrac{\sqrt{n^2}}{\sqrt{n}}=\sqrt{n} \checkmark$$

$\endgroup$
  • $\begingroup$ For an alternative interpretation of the same concept, divide by $n$ and observe that the LHS is the mean value and the RHS is the minimum value of the function $f(x)=1/\sqrt{x}$ on $[n]$ $\endgroup$ – Stella Biderman Apr 4 '17 at 18:30
17
$\begingroup$

Integrals:

$$\sum_{k=1}^n\frac1{\sqrt n}\ge\int_1^{n+1}\frac1{\sqrt x}\ dx=2\sqrt{n+1}-2$$

And it's very easy to check that

$$2\sqrt{n+1}-2\ge\sqrt n$$

for $n\ge2$.

A visuallization of this argument:

enter image description here

From the red lines down, that area represents a sum. From the blue line down, that represents an integral. Clearly, the integral is smaller than the sum.

$\endgroup$
  • $\begingroup$ :Is there a visual explanation for that proof ? $\endgroup$ – Khosrotash Feb 18 '17 at 0:16
  • $\begingroup$ Of course. Give me a few moments... $\endgroup$ – Simply Beautiful Art Feb 18 '17 at 0:16
  • $\begingroup$ thanks a lot .it was interesting $\endgroup$ – Khosrotash Feb 18 '17 at 0:18
  • $\begingroup$ No problem. The few moments are over :-) $\endgroup$ – Simply Beautiful Art Feb 18 '17 at 0:20
  • 1
    $\begingroup$ Interestingly we can obtain the same bound without appealing to integrals. I've posted a solution herein and would like to hear your thoughts. ;-)) -Mark $\endgroup$ – Mark Viola Feb 18 '17 at 6:05
12
$\begingroup$

I thought it might be instructive to present a simple approach that yields a much tighter bound than requested in the OP, and that relies on nothing more than telescoping series and straightforward arithmetic. To that end, we now proceed.


We begin with the telescoping series

$$\sum_{k=1}^{n}\left(\sqrt{k+1}-\sqrt{k}\right)=\sqrt{n+1}-1 \tag 1$$


Inasmuch as $\sqrt{k+1}-\sqrt{k}=\frac{1}{\sqrt{k+1}+\sqrt{k}}$, we can write $(1)$ as

$$\sum_{k=1}^{n}\left(\frac{1}{\sqrt{k+1}+\sqrt{k}}\right)=\sqrt{n+1}-1 \tag 2$$


Then, using $\sqrt{k+1}>\sqrt k$, we have the inequality

$$\sum_{k=1}^{n}\left(\frac{1}{2\sqrt{k}}\right)>\sqrt{n+1}-1$$

from which we see that

$$\bbox[5px,border:2px solid #C0A000]{\sum_{k=1}^{n}\frac{1}{\sqrt{k}}> 2(\sqrt {n+1}-1)} \tag 3$$


Note that $(3)$ provides a much tighter bound for the summation of interest than the one requested in the OP since

$$\sum_{k=1}^n\frac{1}{\sqrt k}>2(\sqrt {n+1} -1)> \sqrt n $$

for $n\ge 2$. It's easy to see that $\sum_{k=1}^n \frac1{\sqrt k} = \sqrt n $ for $n=1$.

And we are done!

Tools Used: Telescoping Series and straightforward arithmetic

$\endgroup$
  • $\begingroup$ (+1) I find answers such as this very appealing. What made you think of telescoping? $\endgroup$ – Plopperzz Feb 18 '17 at 7:01
  • $\begingroup$ @Plopperzz Thank you! Much appreciative. If we use the first term of the EMSF it is $2(\sqrt n - 1)$. This looks like the result of a telescoping series. -Mark $\endgroup$ – Mark Viola Feb 18 '17 at 7:25
  • $\begingroup$ (+1) very nicely done. Very nice use of the difference of two squares. $\endgroup$ – Simply Beautiful Art Feb 18 '17 at 11:23
  • $\begingroup$ (+1) Nice. though too much yellow for my taste. A little typo at the end, should be $\ge \sqrt n$. $\endgroup$ – zwim Feb 18 '17 at 13:47
  • 1
    $\begingroup$ "I really appreciate it." And now we see the hazard from using a "not-so-smart" phone to post here. $\endgroup$ – Mark Viola Feb 18 '17 at 16:28
6
$\begingroup$

By the generalized mean inequality the harmonic mean is no larger than the quadratic mean:

$$ \require{cancel} \cfrac{n}{\cfrac{1}{\sqrt{1}}+\cfrac{1}{\sqrt{2}}+\cdots+\cfrac{1}{\sqrt{n}}} \;\le\; \sqrt{\frac{(\sqrt{1})^2+(\sqrt{2})^2+\cdots+(\sqrt{n})^2}{n}} = \sqrt{\frac{\cancel{n}(n+1)}{2\,\cancel{n}}} $$

$$ \implies \quad \cfrac{1}{\sqrt{1}}+\cfrac{1}{\sqrt{2}}+\cdots+\cfrac{1}{\sqrt{n}} \;\ge\; \sqrt{\frac{2\,n^2}{n+1}} \;\ge\; \sqrt{n} $$

$\endgroup$
  • 1
    $\begingroup$ Nice one, I compared $M_0$ and $M_1$ while comparing $M_{-1}$ and $M_2$ was bringing the result directly. $\endgroup$ – zwim Feb 18 '17 at 2:53
5
$\begingroup$

Using arithmetic and geometric means inequality :

$\displaystyle{\frac{1}{\sqrt 1}+\frac{1}{\sqrt 2}+..+\frac{1}{\sqrt n}\ge n\,\sqrt[n]{\frac{1}{\sqrt 1\sqrt 2..\sqrt n}}\ge n\,(n!)^{-\frac1{2n}}}$

We can get an asymptotic result using Stirling formula :

$n\,(n!)^{-\frac1{2n}}\sim n\left(\sqrt{2\pi n}({\frac ne})^n\right)^{-\frac1{2n}}=\frac{\sqrt e}{\sqrt[4n]{2\pi}}\times n^{1-\frac1{4n}}\times\sqrt n=C(n)\sqrt n$ with $C(n)\to \sqrt[4]e$

Since $\sqrt[4]e\ge 1$ then $C(n)\sqrt n\ge\sqrt n$ for some $n$.

It is not as good as in the other methods, but it presents another idea.

$\endgroup$
  • 1
    $\begingroup$ One may acquire exact inequalities by noting that:$$n!=\exp\left[\sum\ln(k)\right]\le\exp\left[\int\ln(x)\ dx\right]=e\sqrt n\left(\frac ne\right)^n$$ $\endgroup$ – Simply Beautiful Art Feb 18 '17 at 1:02
  • $\begingroup$ I'm not sure what you mean, but since the $n!$ is raised to a negative power, we must find an upper bound, which flips to a lower bound, which then provides what we need quite nicely. $\endgroup$ – Simply Beautiful Art Feb 18 '17 at 1:14
  • $\begingroup$ Yes, nice one :p $\endgroup$ – zwim Feb 18 '17 at 1:14

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.