13
$\begingroup$

I am just starting out learning mathematical induction and I got this homework question to prove with induction but I am not managing.

$$\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$$

Perhaps someone can help me out I don't understand how to move forward from here: $$\sum\limits_{k=1}^{n+1}{\frac{1}{\sqrt{k}}+\frac{1}{\sqrt{n+1}}\ge \sqrt{n+1}}$$ proof and explanation would greatly be appreciated :) Thanks :)

EDIT sorry meant GE not = fixed :)

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You are going to have lots of problems proving that equality, for it is false. (Consider, for example, the case where $n=2$) $\endgroup$ – Mariano Suárez-Álvarez Aug 8 '11 at 16:23
  • $\begingroup$ There is a typo somewhere : your first mathematical line is clearly wrong since $1 + 1/\sqrt{2} > 2$. Did you wish to prove the inequality, as your second line suggests? $\endgroup$ – Patrick Da Silva Aug 8 '11 at 16:24
  • $\begingroup$ The equality is false. If it were true, then $1 + \frac{1}{\sqrt{2}}$ would equal $\sqrt{2}$. But $1+\frac{1}{\sqrt{2}} = \frac{2+\sqrt{2}}{2}$. If this were equal to $\sqrt{2}$, then you would have $2+\sqrt{2}=2\sqrt{2}$, or $2=\sqrt{2}$, which is patently false. $\endgroup$ – Arturo Magidin Aug 8 '11 at 16:24
  • $\begingroup$ You can use the $\mathsf{Euler's \ summation \ formula}$. But as observed by in the previous comments, even I don't think that this is true. $\endgroup$ – user9413 Aug 8 '11 at 16:26
  • 2
    $\begingroup$ Or maybe he just wants to prove $\ge$ $\endgroup$ – GEdgar Aug 8 '11 at 16:26
13
$\begingroup$

If you wanted to prove that $$ \sum_{k=1}^n \frac 1{\sqrt k} \ge \sqrt n, $$ that I can do. It is clear for $n=1$ (since we have equality then), so that it suffices to verify that $$ \sum_{k=1}^{n+1} \frac 1{\sqrt k} \ge \sqrt{n+1} $$ but this is equivalent to $$ \sum_{k=1}^{n} \frac 1{\sqrt k} + \frac 1{\sqrt{n+1}} \ge \sqrt{n+1} \ $$ and again equivalent to $$ \sum_{k=1}^n \frac{\sqrt{n+1}}{\sqrt k} + 1 \ge n+1 $$ so we only need to prove the last statement now, using induction hypothesis. Since $$ \sum_{k=1}^n \frac 1{\sqrt k} \ge \sqrt n, $$ we have $$ \sum_{k=1}^n \frac{\sqrt{n+1}}{\sqrt k} \ge \sqrt{n+1}\sqrt{n} \ge \sqrt{n} \sqrt{n} = n. $$ Adding the $1$'s on both sides we get what we wanted.

Hope that helps,

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Stylistic complaint: you end with «but this is $X\iff Y$», where you meant «but this is (equivalent to) $X$ which holds since $Y$» or something like that. As you wrote it, it appears that the inequality in your second equation is the same thing as a logical equivalence between two inecualities: this does not make much sense. $\endgroup$ – Mariano Suárez-Álvarez Aug 8 '11 at 16:31
  • 1
    $\begingroup$ (After your edit, the same problem subsists: now «this is equivaent to $X\iff Y$» :) ) $\endgroup$ – Mariano Suárez-Álvarez Aug 8 '11 at 16:33
  • $\begingroup$ I was editing a lot : are there any complaints now? =) $\endgroup$ – Patrick Da Silva Aug 8 '11 at 16:37
  • $\begingroup$ I did not understand the last step could you please elaborate? $\endgroup$ – Jason Aug 8 '11 at 16:39
  • $\begingroup$ I multiplied the induction hypothesis by $\sqrt{n+1}$ to get the first inequality, and for the second inequality, since $n+1 > n$, $\sqrt{n+1} > \sqrt n$, so if you multiply those two by $\sqrt{n}$, you get $\sqrt{n+1}\sqrt{n} > \sqrt{n} \sqrt{n}$. That is $\sqrt{n}^2 = n$. Is that okay? $\endgroup$ – Patrick Da Silva Aug 8 '11 at 16:43
15
$\begingroup$

A very short (though non-inductive) proof:

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Nice! Of course there is some hidden induction. [I'd put the $\sqrt k-\sqrt{k-1}$ in parenthesis in the last sum.] $\endgroup$ – Pierre-Yves Gaillard Aug 8 '11 at 18:42
14
$\begingroup$

I won't use induction:

On the left side you have a sum with $n$ terms, the smallest one is $\frac{1}{\sqrt{n}}$. So you get the inequality:

$$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\ldots+\frac{1}{\sqrt{n}}\ge \frac{1}{\sqrt{1}}+(n-1)\frac{1}{\sqrt{n}}=\left(1-\frac{1}{\sqrt{n}}\right)+\sqrt{n}$$

And now you can see easily that the right hand side is larger than $\sqrt{n}$, for all $n>1$.

I hope this helps.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Couldn't you just write "greater than $n/\sqrt{n} = \sqrt n$" instead of keeping the $1/\sqrt{1}$ aside? $\endgroup$ – Patrick Da Silva Aug 8 '11 at 16:33
  • $\begingroup$ By the way, you can write \ge for $\ge$. $\endgroup$ – Patrick Da Silva Aug 8 '11 at 16:36
  • $\begingroup$ Thanks for $\ge$. Don't get your question right. You mean $$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\ldots+\frac{1}{\sqrt{n}}\ge \frac{n}{\sqrt{n}}=\sqrt{n}$$? $\endgroup$ – ulead86 Aug 8 '11 at 16:42
  • $\begingroup$ Exactly. Easier, isn't it? $\endgroup$ – Patrick Da Silva Aug 8 '11 at 17:05
  • 4
    $\begingroup$ @DDaniel: The induction is not explicit, though in fact there is an implicit induction hidden in the $\dots$. Upvote for a probably simplest solution! $\endgroup$ – André Nicolas Aug 8 '11 at 17:05
7
$\begingroup$

You know that ${\displaystyle \sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}}$, and your goal is to show that ${\displaystyle \sum\limits_{k=1}^{n+1}{\frac{1}{\sqrt{k}}\ge\sqrt{n+1}}}$. Observe that $$ \sum\limits_{k=1}^{n+1}{\frac{1}{\sqrt{k}} = \sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}}} + {1 \over \sqrt{n+1}}$$ $$\geq \sqrt{n} + {1 \over \sqrt{n+1}}$$ You use the induction hypothesis in the above line. So what you need to show is $$\sqrt{n} + {1 \over \sqrt{n+1}} \geq \sqrt{n+1}$$ At this point you can basically try to fool around with the algebra to get it to work out. One example of this would be to multiply both sides by $\sqrt{n+1}$, getting $$\sqrt{n(n+1)} + 1 \geq n + 1$$ Or equivalently, $$\sqrt{n(n+1)} \geq n$$ Squaring both sides gives $$n^2 + n \geq n^2$$ This last equation is obviously true. To make the argument rigorous, you just observe that these steps are reversible; going in the opposite direction from above takes you from $n^2 + n \geq n^2$ to $\sqrt{n} + {1 \over \sqrt{n+1}} \geq \sqrt{n+1}$.

Some people might not like doing this sort of reversal-of-steps argument, but it does have an advantage that you don't really have to see anything clever to do it; ususally playing around with the algebra enough will eventually lead to something obvious.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Great thanks, this is the solution I got to Though my algebra proof was different $\endgroup$ – Jason Aug 8 '11 at 19:56
5
$\begingroup$

Using the same identity that Sasha did, $$ \begin{align} \sqrt{k+1}-\sqrt{k}&=\frac{1}{\sqrt{k+1}+\sqrt{k}}\\ &\le\frac{1}{2\sqrt{k}} \end{align} $$ We can sum and multiply by $2$ to get $$ 2(\sqrt{n+1}-1)\le\sum_{k=1}^n\frac{1}{\sqrt{k}} $$ Which for most $n$ is stronger.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can you give a characterization of the $n$'s for which is it stronger? =O Kidding. +1 $\endgroup$ – Patrick Da Silva Aug 8 '11 at 23:24
  • $\begingroup$ @Patrick Da Silva: Any integer bigger than $\frac{16}{9}$ $\endgroup$ – robjohn♦ Aug 9 '11 at 0:02
  • $\begingroup$ Lollll you guys are so serious. XD Anyway that's cool. $\endgroup$ – Patrick Da Silva Aug 9 '11 at 1:12
  • $\begingroup$ @Patrick Da Silva: I was joking, too, but maybe my sense of humor is off . o O (integer bigger than $\frac{16}{9}$...) :-p $\endgroup$ – robjohn♦ Aug 9 '11 at 2:23
  • 1
    $\begingroup$ I know it was a joke, that's why I added the XD in the end. If I had believed you were truly serious I would've been pissed. $\endgroup$ – Patrick Da Silva Aug 9 '11 at 2:24
5
$\begingroup$

For those who strive for non-induction proofs...

Since $\frac 1{\sqrt k} \ge \frac 1{\sqrt n}$ for $1 \le k \le n$, we actually have $$ \sum_{i=1}^n \frac 1{\sqrt k} \ge \sum_{i=1}^n \frac 1{\sqrt n} = \frac n{\sqrt n} = \sqrt n. $$

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ This shows how understated the original estimate was. It's like saying that $\sum_{k=1}^n k\le n^2$. $\endgroup$ – robjohn♦ Aug 8 '11 at 23:41
  • $\begingroup$ I know... and it also shows why I'm so impressed that people made a huuuge deal about finding 430423 proofs for this. $\endgroup$ – Patrick Da Silva Aug 8 '11 at 23:42
  • $\begingroup$ @robjohn Talking of understated, I'm usually happy with $\sum \limits_{k=1}^{n} k = O(n^2)$. :-) $\endgroup$ – Srivatsan Jan 4 '12 at 21:58

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.