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 :)

  • 1
    You are going to have lots of problems proving that equality, for it is false. (Consider, for example, the case where $n=2$)2011-08-08
  • 0
    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?2011-08-08
  • 0
    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.2011-08-08
  • 0
    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.2011-08-08
  • 2
    Or maybe he just wants to prove $\ge$2011-08-08
  • 0
    @Chandra: If he is just learning mathematical induction, then he probably doesn't know Euler's summation formula.2011-08-08
  • 0
    @Gedgar: True. Sorry for the comments. I just suggested an another way of doing it.2011-08-08
  • 0
    There are plenty of elementary ways to do it, as Daniel suggested in his answer. OP doesn't need help in proving the statement in a general manner, he wants help on using induction to do it. Sure there are other ways. ^_^2011-08-08

6 Answers 6

5

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

  • 2
    This shows how understated the original estimate was. It's like saying that $\sum_{k=1}^n k\le n^2$.2011-08-08
  • 0
    I know... and it also shows why I'm so impressed that people made a huuuge deal about finding 430423 proofs for this.2011-08-08
  • 0
    @robjohn Talking of understated, I'm usually happy with $\sum \limits_{k=1}^{n} k = O(n^2)$. :-)2012-01-04
15

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

  • 0
    Nice! Of course there is some hidden induction. [I'd put the $\sqrt k-\sqrt{k-1}$ in parenthesis in the last sum.]2011-08-08
14

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.

  • 0
    Couldn't you just write "greater than $n/\sqrt{n} = \sqrt n$" instead of keeping the $1/\sqrt{1}$ aside?2011-08-08
  • 0
    By the way, you can write \ge for $\ge$.2011-08-08
  • 0
    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}$$?2011-08-08
  • 0
    Exactly. Easier, isn't it?2011-08-08
  • 4
    @DDaniel: The induction is not explicit, though in fact there is an implicit induction hidden in the $\dots$. Upvote for a probably simplest solution!2011-08-08
  • 0
    Daniel: so you proved the thing for every $n\ge2$ only... :-) (Corrected some typos in your answer, please look at the source to see the modifications.)2011-08-08
  • 0
    Daniel and @Didier: Nice job! I think it would also be better to remove "the equation:". ("Equation" suggests equalities, not inequalities, nor a combination of both.) (To Didier: entre deux mots, choisissons le moindre!)2011-08-08
  • 0
    Daniel: remains the odd treatment of the term $1/\sqrt1$, you could modify this part as well... (@Pierre-Yves: you are absolutely right, *equation* was simply inadequate there and I missed it.)2011-08-08
  • 0
    @Didier: Correct quotation: "Entre deux mots, il faut choisir le moindre." (Paul Valéry) [My suggestion was to write just "you get" (even without the colon (:)), because there is an inequality *and* an equality. (Whence the quotation). Sorry!]2011-08-08
  • 0
    @Didier: If I were the author, I'd put a period (.) at the end of the display. (You seem to do the same.)2011-08-08
  • 0
    @Pierre-Yves: I do (use periods where they are needed) but I seem to remember there is some debate about this when at the end of displays. Re "you get", I am not the one who did the last modification there; if I was I would have applied your suggestion.2011-08-08
  • 0
    @Didier: OK! I thought my suggestion wasn't clear enough (which would have made the quotation impossible to understand). [A tougher exercise would be to translate the quotation into English ;)]2011-08-08
13

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,

  • 1
    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.2011-08-08
  • 1
    (After your edit, the same problem subsists: now «this is equivaent to $X\iff Y$» :) )2011-08-08
  • 0
    I was editing a lot : are there any complaints now? =)2011-08-08
  • 0
    I did not understand the last step could you please elaborate?2011-08-08
  • 0
    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?2011-08-08
  • 0
    you still need to prove that $\sum\limits_{k=1}^{n}{\frac{\sqrt{n+1}}{\sqrt{k}}}$ is bigger then n though don't you?2011-08-08
  • 0
    That is what I proved. Using induction hypothesis I know that $$ \sum_{k=1}^n \frac 1{\sqrt k} \ge \sqrt n. $$ Multiply both sides of my inequality by $\sqrt{n+1}$ and follow the steps from my last comment to prove that $$ \sum_{k=1}^n \frac{\sqrt{n+1}}{\sqrt{k}} \ge n. $$2011-08-08
  • 0
    I see how you got to that inequity but what makes it true? (I feel stupid :P)2011-08-08
  • 0
    If you see how I got it then you see why it is true... I assumed that what I wanted to prove was true up to $n$, so to show it is true at $n+1$, I assume it is true at $n$ (i.e. that the following inequality holds : $$ \sum_{k=1}^n \frac 1{\sqrt k} \ge \sqrt n $$ that is, induction hypothesis) and using this inequality I deduce that $$ \sum_{k=1}^n \frac{\sqrt{n+1}}{\sqrt k} \ge n. $$ To deduce it I use the steps above. Is that what you wanted me to clarify?2011-08-08
  • 0
    I Think I get it now :) Thanks for your patience :)2011-08-08
  • 0
    No problem! Anytime.2011-08-08
7

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.

  • 0
    Great thanks, this is the solution I got to Though my algebra proof was different2011-08-08
5

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.

  • 0
    Can you give a characterization of the $n$'s for which is it stronger? =O Kidding. +12011-08-08
  • 0
    @Patrick Da Silva: Any integer bigger than $\frac{16}{9}$2011-08-09
  • 0
    Lollll you guys are so serious. XD Anyway that's cool.2011-08-09
  • 0
    @Patrick Da Silva: I was joking, too, but maybe my sense of humor is off . o O (integer bigger than $\frac{16}{9}$...) :-p2011-08-09
  • 1
    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.2011-08-09
  • 0
    Creative telescoping is always quite interesting (+1)2017-10-02