0
$\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 ?

  • 0
    @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.2012-01-04

3 Answers 3

2

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.

  • 0
    @Mariano Done, thanks.2012-01-04
5

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.

  • 1
    For a discrete analog see my answer.2012-01-04
3

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.

  • 1
    @Asa$f$ 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.2012-01-04