16
$\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 :)

$\endgroup$
8
  • 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$ Aug 8, 2011 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$ Aug 8, 2011 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$ Aug 8, 2011 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, 2011 at 16:26
  • 2
    $\begingroup$ Or maybe he just wants to prove $\ge$ $\endgroup$
    – GEdgar
    Aug 8, 2011 at 16:26

6 Answers 6

18
$\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,

$\endgroup$
11
  • 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$ Aug 8, 2011 at 16:31
  • 1
    $\begingroup$ (After your edit, the same problem subsists: now «this is equivaent to $X\iff Y$» :) ) $\endgroup$ Aug 8, 2011 at 16:33
  • $\begingroup$ I was editing a lot : are there any complaints now? =) $\endgroup$ Aug 8, 2011 at 16:37
  • $\begingroup$ I did not understand the last step could you please elaborate? $\endgroup$
    – Jason
    Aug 8, 2011 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$ Aug 8, 2011 at 16:43
18
$\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} $$

$\endgroup$
1
  • $\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$ Aug 8, 2011 at 18:42
16
$\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.

$\endgroup$
12
  • $\begingroup$ Couldn't you just write "greater than $n/\sqrt{n} = \sqrt n$" instead of keeping the $1/\sqrt{1}$ aside? $\endgroup$ Aug 8, 2011 at 16:33
  • $\begingroup$ By the way, you can write \ge for $\ge$. $\endgroup$ Aug 8, 2011 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, 2011 at 16:42
  • $\begingroup$ Exactly. Easier, isn't it? $\endgroup$ Aug 8, 2011 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$ Aug 8, 2011 at 17:05
9
$\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.

$\endgroup$
1
  • $\begingroup$ Great thanks, this is the solution I got to Though my algebra proof was different $\endgroup$
    – Jason
    Aug 8, 2011 at 19:56
7
$\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.

$\endgroup$
6
  • $\begingroup$ Can you give a characterization of the $n$'s for which is it stronger? =O Kidding. +1 $\endgroup$ Aug 8, 2011 at 23:24
  • $\begingroup$ @Patrick Da Silva: Any integer bigger than $\frac{16}{9}$ $\endgroup$
    – robjohn
    Aug 9, 2011 at 0:02
  • $\begingroup$ Lollll you guys are so serious. XD Anyway that's cool. $\endgroup$ Aug 9, 2011 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, 2011 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$ Aug 9, 2011 at 2:24
7
$\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. $$

$\endgroup$
3
  • 3
    $\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, 2011 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$ Aug 8, 2011 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, 2012 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.