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

  • 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 indu$c$$t$ion to do it. Sure there are other ways. ^_^2011-08-08

6 Answers 6

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
    Creative telescoping is always quite interesting (+1)2017-10-02
17

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
16

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,

  • 0
    No problem! Anytime.2011-08-08
15

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
    @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
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
6

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

  • 0
    @robjohn Talking of understated, I'm usually happy with $\sum \limits_{k=1}^{n} k = O(n^2)$. :-)2012-01-04