1
$\begingroup$

Possible Duplicate:
Proof of an inequality: $\sqrt{n} < \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}}$

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 ?

$\endgroup$
6
  • 1
    $\begingroup$ Maybe you could tell us what you've tried so far? Possibly, you weren't so far away from the right path. $\endgroup$ Jan 4, 2012 at 19:37
  • $\begingroup$ 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.) $\endgroup$
    – Srivatsan
    Jan 4, 2012 at 19:39
  • $\begingroup$ 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. $\endgroup$ Jan 4, 2012 at 20:02
  • $\begingroup$ @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. $\endgroup$
    – Srivatsan
    Jan 4, 2012 at 20:04
  • 1
    $\begingroup$ @Srivatsan: It is a natural type of homework exercise at the beginnings of induction. About "duplicate in spirit," we will be closing a large proportion of the questions if that is the criterion. What I was trying to do in my answer was to point to the unclever but essentially automatic solution that a student might arrive at. $\endgroup$ Jan 4, 2012 at 20:15

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I am curious, because of the clever trick you used, as to how you got there? Why did the problem scream for that trick? $\endgroup$
    – user12205
    Jan 4, 2012 at 20:38
  • 1
    $\begingroup$ For a discrete analog see my answer. $\endgroup$ Jan 4, 2012 at 20:41
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ finally understood this! thanks a lot! $\endgroup$
    – Asaf
    Jan 4, 2012 at 20:51
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 4, 2012 at 21:03
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 4, 2012 at 22:04
2
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ It would help the reader if you made explicit what f is. $\endgroup$ Jan 4, 2012 at 20:41
  • $\begingroup$ @Mariano Done, thanks. $\endgroup$ Jan 4, 2012 at 20:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.