5

I have the following inequality to prove with induction:

$$P(n): \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots\frac{1}{\sqrt{n}}>2-\frac{2}{n}, \forall n\in \mathbb{\:N}^*$$

I tried to prove $P(n+1)$:

Let $S = \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{n+1}}\Rightarrow$

$$P(n+1):S>2-\frac{2}{n+1}$$

I got into this point and I think it is all wrong, but I'll write it here also:

$$S>\frac{2(n+1) + n\sqrt{n+1}}{n(n+1)}$$

and I don't know what to do next... Could anybody help me, please? I would also like to know if there's any other smarter way of solving this kind of exercises.

Martin Sleziak
  • 53,687
Victor
  • 437
  • 1
    It might be easier to look at $P(1),P(2),P(3)$ and then wonder whether there is an error in the question – Henry Dec 17 '14 at 07:54
  • There is not any error in the question. I might have gone on the wrong path. Because $P(1): 1>0 \Rightarrow true$, $P(2):2+\sqrt{2}>2 \Rightarrow true$ and $P(3): 6+3\sqrt{2}+2\sqrt{3}>8 \Rightarrow true$ – Victor Dec 17 '14 at 07:59
  • 6
    But $\dfrac{1}{\sqrt{1}}+\dfrac{1}{\sqrt{2}}+\dfrac{1}{\sqrt{3}} \gt 2 \gt 2-\dfrac2n$ for all positive $n$ – Henry Dec 17 '14 at 08:02
  • Assume $P(n-1)$ is true. then: $$ \sum_{k=1}^{n-1}{1\over\sqrt{k}} < 2-{{2}\over{n-1}} \ \sum_{k=1}^{n}{1\over\sqrt{k}} ,<, 2+{{1}\over{\sqrt{n}}}-{{2}\over{n-1}} \ $$ Note that: $$ {2\over{n}}<{{2}\over{n-1}}-{{1}\over{\sqrt{n}}} \ $$ – SomeStrangeUser Dec 17 '14 at 08:02
  • Sure, what @Henry says is true. Moreover, it shows that no induction is needed, since it immediately proves the requested inequality for $n\ge3$. I suspect whoever posed the problem did not think it through … that can happen from time to time, to the best of us. – Harald Hanche-Olsen Dec 17 '14 at 08:11
  • And if I prove for $n\ge3$, won't I need to say anything more? – Victor Dec 17 '14 at 08:13
  • Exactly. As an exercise in induction, the problem is unfortunately worthless. (On a side note, be careful in writing stuff like $P(2):2+\sqrt{2}>2 \Rightarrow true$ like you did above, for any statement, true or false, implies any true statement. It's one of the oddities of mathematical logic as opposed to everyday use of language. Perhaps you meant the arrow to mean “evaluates to” or something like that, but then you should have chosen a different style arrow to avoid confusion.) – Harald Hanche-Olsen Dec 17 '14 at 08:17
  • I am sorry about that. I had written them in my notebook, and I hurried up to write them here – Victor Dec 17 '14 at 08:19
  • 2
    A more interesting question might be showing the sum is between $\sqrt{n}$ and $2\sqrt{n}$ – Henry Dec 17 '14 at 08:21

1 Answers1

1

Initial comment: Begin by noting that, for all $n\geq 1$, we have that $$ n(\sqrt{n}-2)+2>0\Longleftrightarrow n\sqrt{n}-2n+2>0\Longleftrightarrow \color{red}{\sqrt{n}>2-\frac{2}{n}}.\tag{1} $$ Thus, it suffices for us to prove the proposition $P(n)$ for all $n\geq 1$ where $$ P(n): \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{n}}\geq \sqrt{n}.\tag{2} $$ If we can prove $(2)$, then we will have proven $$ \color{blue}{\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{n}}}\color{red}{\geq\sqrt{n}}\color{blue}{> 2-\frac{2}{n}}, $$ as desired. I'm sure you can handle the proof of $(1)$ quite easily.

Claim: For $n\geq 1$, let $P(n)$ denote the statement $$ P(n): \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{n}}\geq \sqrt{n}. $$

Base step: $P(1)$ holds since $1\geq\sqrt{1}$ is true.

Before induction step: Consider the following inequality for any $x\geq 1$: $$ \sqrt{x}+\frac{1}{\sqrt{x+1}}>\sqrt{x+1}\tag{3}. $$ Briefly, observe that for $x\geq 1, \sqrt{x(x+1)}>x$; thus, $\sqrt{x(x+1)}+1>x+1$. Dividing by $\sqrt{x+1}$ proves $(3)$. The purpose of $(3)$ is to streamline the calculations below in the inductive step.

Inductive step: Fix some $k\geq 1$ and suppose that $P(k)$ is true. Then \begin{align} \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{k}}+\frac{1}{\sqrt{k+1}} &\geq \sqrt{k}+\frac{1}{\sqrt{k+1}}\tag{by $P(k)$}\\[1em] &> \sqrt{k+1},\tag{by $(3)$} \end{align} which shows that $S(k+1)$ follows. This concludes the inductive step.

Thus, for all $n\geq 1, P(n)$ is true. $\blacksquare$

Daniel W. Farlow
  • 22,531
  • The stronger claim is also shown in several other posts: See http://math.stackexchange.com/questions/56335/proving-sum-limits-k-1n-frac1-sqrtk-ge-sqrtn-with-induction and the psots which are linked there. – Martin Sleziak Mar 22 '15 at 10:01