# proving Mathematical Induction [duplicate]

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

I've tried to work on this equation for about 4-5 Hours.
I'm trying to show that the following equation is true with induction:

$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}>2(\sqrt{n+1}-1)$

after about 4-5 hours and numerous attempts I couldn't really get it to work out.
Any ideas ?

-

## marked as duplicate by Srivatsan, Asaf Karagila, t.b., Matt N., Thomas AndrewsJan 4 '12 at 20:07

Maybe you could tell us what you've tried so far? Possibly, you weren't so far away from the right path. –  Thomas Belulovich Jan 4 '12 at 19:37
This problem has appeared multiple times; e.g., see this and this. I am voting to close this as a duplicate. (And strangely all three posters want a solution using induction; I wonder why.) –  Srivatsan Jan 4 '12 at 19:39
The inequalities are in fact different from this one. But whether or not the question is closed, I assume the OP will have access to the answers. –  André Nicolas Jan 4 '12 at 20:02
@AndréNicolas Yes, you are correct. But I do feel this is a duplicate in spirit; also there are answers proving even the stronger bound (in fact the very same bound). I linked to two such posts in my previous comment. –  Srivatsan Jan 4 '12 at 20:04
@Asaf, I am not suggesting you (or the other posters) are hiding something; merely surprised that the very same problem has appeared multiple times with the same restriction: to use induction. It seems like quite a popular homework exercise. :-) –  Srivatsan Jan 4 '12 at 20:07
show 1 more comment

There are ways other than induction (such as comparison with an integral) that have much clearer intuitive content. But let's stick with induction. We need to deal with the induction step. Suppose that we know for a given $k$ that $$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{k}}>2(\sqrt{k+1}-1).\qquad\qquad(\ast)$$ We wish to show that $$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{k}}+ \frac{1}{\sqrt{k+1}} > 2(\sqrt{k+2}-1).\qquad\qquad(\ast\ast)$$

By $(\ast)$, we have $$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{k}}+ \frac{1}{\sqrt{k+1}} >2(\sqrt{k+1}-1)+ \frac{1}{\sqrt{k+1}}.$$ We will be finished if we can prove that $$2(\sqrt{k+1}-1)+ \frac{1}{\sqrt{k+1}} >2(\sqrt{k+2}-1).$$ Equivalently, by a little algebra, we want to show that $$2\sqrt{k+1}+ \frac{1}{\sqrt{k+1}} >2\sqrt{k+2}.$$ Equivalently, by a little more algebra, we want to show that $$2(k+1)+1>2\sqrt{k+2}\sqrt{k+1}$$ (we multiplied throgh by the positive number $\sqrt{k+1}$). So we want to show that $$2k+3 >2\sqrt{k^2+3k+2}.$$ Since both sides are positive, this is equivalent to showing that $$(2k+3)^2>4(k^2+3k+2).$$ Now we are finished, for the left side is $4k^2+12k+9$, while the right side is $4k^2+12k+8$, so the left side is greater than the right side.

-
finally understood this! thanks a lot! –  Asaf Jan 4 '12 at 20:51
As I indicated, the approach through the integral is more sensible. It ties in nicely with the integral test for convergence of series, also with (widely spread out) Riemann sums. Draw a rectangle base $[1,2]$ height $1$, then rectangle base $[2,3]$ height $1/\sqrt{2}$, then base $[3,4]$, height $1/\sqrt{3}$ and so on. Our sum is the sum of the areas of the rectangles. Now draw the curve $y=1/\sqrt{x}$. The region below this curve, from $1$ to $n+1$, is contained in the union of our rectangles, so has smaller area. Similarly you can get an inequality in the other direction. –  André Nicolas Jan 4 '12 at 21:03
@Asaf The above answer is a special case of a proof of positivity by telescopy. My answer explains this more conceptual viewpoint. It shows how to reduce the proof to a mechanical polynomial computation. Moreover, unlike above, nothing is pulled out of a hat. –  Bill Dubuque Jan 4 '12 at 22:04

This is not really an induction, but the problem screams for this:

The sum on the left is greater than $\int_1^{n+1}x^{-1/2}\,\mathrm dx$. Evaluate this integral.

-
I am curious, because of the clever trick you used, as to how you got there? Why did the problem scream for that trick? –  user12205 Jan 4 '12 at 20:38
For a discrete analog see my answer. –  Bill Dubuque Jan 4 '12 at 20:41
HINT  To prove $\rm\ f(n) > 0\$ it suffices to show that $\rm\:f(1) > 0\$ and that $\rm\:f\:$ is increasing $\rm\:f(n+1) \ge f(n)\:.\:$ But calculating $\rm\:f(n+1)-f(n)\:$ for your $\rm\:f(n)\:$ we get $\rm\: (2\:n+3 - 2\:((n+1)(n+2))^{1/2})/(n+1)^{1/2},\:$ which is $\ge 0\$ by $\rm\ (2\:n+3)^2-4\:(n+1)\:(n+2)\ =\ 1\:,\:$ so its numerator is $> 0\$ (take sqrt's).
Note: above $\rm\:f(n)\:$ is the term you wish to prove $>0\:,\$ i.e. $\rm\ f(n)\: =\: \sum_{k=1}^n\:1/\sqrt{k}\ -\ 2(\sqrt{n+1}-1)\:.$
Note that this certainly is a proof by induction, the induction being the triviality that an increasing function on $\rm\:\mathbb N\:$ that starts positive $\rm\:(f(1)> 0)\:$ remains positive for all $\rm\:n > 1\:.$ Once you complete this trivial inductive proof you'll have not only a proof for the given problem, but you'll also have a very useful lemma that you can reuse many times to handle similar problems. Notice that a little bit of abstraction yielded not only a simpler proof (compared to brute-force) but also a much more general result with wide applicability. This is not so rare. One should aways perform a conceptual analysis before diving in to brute-force approaches.
Conceptually this may be viewed as proof of positivity by telescopy, i.e. that a sum of positive terms remains positive, since above we effectively rewrote the expression as the sum of its first differences, then proved those differences positive. Similarly telescopic techniques suffice to reduce many inductive proofs to analogous trivial inductions, e.g. that $\rm\: 1^n = 1\:.\:$ For much further discussion see my many prior posts on telescopic topics.