Induction proof that a square of a sum is less than a half

Question

I have to prove by induction that $$\left(\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{2n}\right)^2< \frac12$$ for $n\ge1$. Taking the base case, assuming the statement is valid and continuing to prove for $n+1$ I get $$\left(\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{2n}+\frac{1}{2n+2}\right)<\frac{1}{\sqrt2}$$ Now I substitute $\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{2n}=\frac{1}{\sqrt2}-\epsilon$ where $\epsilon>0$ and depends on $n$. $$\frac{1}{\sqrt2}-\epsilon+\frac{1}{2n+2}<\frac{1}{\sqrt2}\Rightarrow \frac{1}{2n+2}<\epsilon$$ Which is true. Is this proof a valid induction proof?

Answer 1

$\frac {1}{n+1} + \frac {1}{n+2}\cdots \frac {1}{2n} < \frac {\sqrt2}{2}$

We are going to run into a little bit of trouble with induction. But lets start that way. The base case: $\frac 12 < \frac {\sqrt 2}{2}$

Inductive hypothesis:

Suppose $\sum_\limits{i=n+1}^{2n} \frac 1i < \frac {\sqrt 2}2 $

Show that: $\sum_\limits{i=n+2}^{2n+2} \frac 1i < \frac {\sqrt 2}2 $

$\sum_\limits{i=n+2}^{2n+2} \frac 1i = \sum_\limits{i=n+1}^{2n} \frac 1i + \frac 1{2n+1} + \frac 1{2n+2} - \frac 1{2n+1} = \sum_\limits{i=n+1}^{2n} \frac 1i + \frac 1{2n+1} - \frac 1{2n+2}$

That is interesting. It doesn't really help us with proof by induction induction, but with a little algebra we can show that.

$\sum_\limits{i=n+1}^{2n} \frac 1i = \sum_\limits{i=1}^{2n} \frac {(-1)^i}{i}=\sum_\limits{i=1}^{n} \frac {1}{(2i-1)(2i)}$ and $\lim_\limits{n\to\infty} \sum_\limits{i=1}^{2n} \frac {(-1)^i}{i} = \ln 2$

The partial sums of $\sum_\limits{i=1}^{n} \frac {1}{(2i-1)(2i)}$ are strictly increasing and the series converges to $\ln 2$ and $\ln 2 < \sqrt 2$ we have a proof, just not by induction.

If we want to do a proof by induction.

prove: $\frac {1}{n+1} + \frac {1}{n+2}\cdots \frac {1}{2n} < \frac {\sqrt2}{2} - \frac {1}{2n^2}$

Unfortunately the doesn't satify the base case unless $n>2$ nonetheless is is easy enough to show that $\frac 12< \frac {\sqrt 2}{2}$ and $\frac 13 + \frac 14 < \frac {\sqrt 2}{2}$ and use induction for the rest.

The base case $n=3: \frac 14 + \frac 15+ \frac 16 = \frac{37}{60} < \frac {\sqrt 2}{2} - \frac 1{18}$

Inductive hypothesis $\sum_\limits{i=n+1}^{2n} \frac 1i < \frac {\sqrt 2}2 - \frac 1{2n^2}$

we will show that

$\sum_\limits{i=n+2}^{2n+2} \frac 1i < \frac {\sqrt 2}2 - \frac 1{2(n+1)^2}$

$\sum_\limits{i=n+2}^{2n+2} \frac 1i = $$\sum_\limits{i=n+1}^{2n} \frac 1i + \frac{1}{2n+1} - \frac{1}{2n+2}$

by the inductive hypothesis:

$\sum_\limits{i=n+2}^{2n+2} \frac 1i< \frac {\sqrt 2}{2} - \frac 1{2n^2} + \frac 1{(2n+1)(2n+2)}<\frac {\sqrt 2}{2} - \frac 1{2(n+1)^2}$

Answer 2

You need to more clearly separate between the base case and the induction step. In fact, you really don't show your base case.

For the base case, you need to consider $n=1$, i.e. verify that $(\frac{1}{2})^2 < \frac{1}{2}$ ... which it is.

For the step: what you want to show is:

$$\left(\frac{1}{(n+1)+1}+\frac{1}{(n+1)+2}+...+\frac{1}{2(n+1)}\right)^2<\frac{1}{2}$$

i.e.

$$\left(\frac{1}{n+2}+\frac{1}{n+3}+...+\frac{1}{2n+2}\right)^2<\frac{1}{2}$$

(so you had that a little big wrong .. you mistakenly included the term $\frac{1}{n+1}$ but excluded the term $\frac{1}{2n+1}$)

on the basis of the inductive hypothesis:

$$\left(\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{2n}\right)^2<\frac{1}{2}$$

And sorry, my math isn't good enough to comment on the actual math to proceed ... but I am a logician so I can tell you about the setup. :)

Answer 3

If $f(n)=\sum_{r=1}^n\dfrac1{n+r}$

$$f(m+1)-f(m)=\dfrac1{m+1}-\left(\dfrac1{2m+1}+\dfrac1{2m+2}\right)=\dfrac1{2m+2}-\dfrac1{2m+1}<0$$

Now $f(1)=?$

Answer 4

To put you of track...

In the induction we assume the assertion $A_n$ holds $$\frac{1}{n+1}+\frac{1}{n+2}+\frac{1}{n+3}+\cdots+\frac{1}{2n-1} +\frac{1}{2n}<\sqrt{2}$$ Using this assumption we need to prove $A_{n+1}$ $$\frac{1}{(n+1)+1}+\frac{1}{(n+1)+2}+\cdots+\frac{1}{2(n+1)-1} +\frac{1}{2(n+1)}<\sqrt{2}$$ that is $$\frac{1}{n+2}+\frac{1}{n+3}+\cdots+\frac{1}{2n}+\frac{1}{2n+1} +\frac{1}{2n+2}<\sqrt{2}$$ Here the left hand side is almost the left hand side of $A_n$.