Induction Question (1 Viewer)

rand_althor · Oct 3, 2015

$$Prove for $n\in \mathbb{N}$, that $\sqrt{n} \leq \sum_{r=1}^{n}\frac{1}{\sqrt{r}} \leq 2\sqrt{n}-1$.$
Not sure how to do this. Tried splitting the inequality up into $\sqrt{n} \leq \sum_{r=1}^{n}\frac{1}{\sqrt{r}}$ and $\sum_{r=1}^{n}\frac{1}{\sqrt{r}} \leq 2\sqrt{n}-1$ and then prove these statements by induction, but I can't prove that they're true for n=k+1. Am I approaching this the wrong way?

Drsoccerball · Oct 3, 2015

Have you tried doing rectangles and trapeziums ?

rand_althor · Oct 3, 2015

Nope - I tried induction as that's what the other questions with this one were about.

How would I use rectangles and trapeziums?

Paradoxica · Oct 3, 2015

I managed to prove the LH inequality. Now working on the right handed one after I type up my proof.

Drsoccerball · Oct 3, 2015

I proved both but im not sure abou the equality of the RHS....
Anyways:
$$ Let $ F(x)= \frac{1}{\sqrt{x}}$

$$ Sum of lower rectangles $ = \sum_{r=1}^n{\frac{1}{\sqrt{r}}}$

$$ Since the graph is always decreasing that means $ f(k) \geq f(k+1)$

$\therefore \sqrt{n} \leq \sum{\frac{1}{\sqrt{r}}}$

$Total exact area would be greater than lower rectangles$

$$ exact area $ = 2 \sqrt{n} -2$

$$ Thus proving the statement since $ -2 \leq -1$

Biggest mission typing that up on my phone... But i dont get the equality on the RHS when i do that method.

Drsoccerball · Oct 3, 2015

Actually i proved 1/sqrt n ...

rand_althor · Oct 3, 2015

Drsoccerball said:
I proved both but im not sure abou the equality of the RHS....
Anyways:
$$ Let $ F(x)= \frac{1}{\sqrt{x}}$

$$ Sum of lower rectangles $ = \sum_{r=1}^n{\frac{1}{\sqrt{r}}}$

$$ Since the graph is always decreasing that means $ f(k) \geq f(k+1)$

$\therefore \sqrt{n} \leq \sum{\frac{1}{\sqrt{r}}}$

Are these the rectangles you are referring to?:

Also I'm lost on that last part I've quoted. How do you reach that conclusion and what does it actually mean?

Drsoccerball · Oct 3, 2015

yes those are the rectangles I am talking about. If $A \leq B-1$

$$ That MUST mean that $ A \leq B$
Via negative omission

Paradoxica · Oct 3, 2015

Paradoxica said:
I managed to prove the LH inequality. Now working on the right handed one after I type up my proof.

$\text{Before we begin, we will prove a helpful inequality.}$
$\text{For } k>0, 4k^2 +4k > 4k^2$
$\Rightarrow 2\sqrt{k^2+k} > 2k$
$\Rightarrow 1+2\sqrt{k^2+k} > 2k +1$
$\text{Now we can begin.}$
$\text{Claim}: \sum_{r=1}^{n}{\frac{1}{\sqrt{r}}}\geq \sqrt{n} \text{ for all } n \in \mathbb{Z}^+$
$\text{Base Cases}: n=1 \text{ is equality}, n= 2 \text{ is inequality.}$
$\text{Assume true for } n=k, \text{ and show this implies } k+1.$
$\text{for } n=k+1, \sum_{r=1}^{k+1}{\frac{1}{\sqrt{r}}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}$
$\text{This follows from the assumption that } n=k \text{ is true.}$
$\left (\sqrt{k}+\frac{1}{\sqrt{k+1}} \right )^2=k+\frac{1}{k+1}+\frac{2\sqrt{k}}{\sqrt{k+1}}=k+\frac{1+2\sqrt{k^2+k}}{k+1}$
$\text{Using the inequality first proven,}$
$\text{we conclude } k+\frac{1+2\sqrt{k^2+k}}{k+1} > k+\frac{2k+1}{k+1}=k+1+\frac{k}{k+1}>k+1$
$\noindent \text{This completes the inductive step and proves } \sum_{r=1}^{k+1}{\frac{1}{\sqrt{r}}}>\sqrt{k+1}, iff it is true for } n=k.$
$\noindent \text{ Since it is true for } n=2, \text{ by the principle of induction, it is true for all } n \in \mathbb{Z}^+$
Equality case can be considered throughout the proof, but I seperated it for some reason.

Drsoccerball said:
yes those are the rectangles I am talking about. If $A \leq B-1$

$$ That MUST mean that $ A \leq B$
Via negative omission

$\text{Wouldn't that be a strict inequality?}$

rand_althor · Oct 3, 2015

Drsoccerball said:
yes those are the rectangles I am talking about. If $A \leq B-1$

$$ That MUST mean that $ A \leq B$
Via negative omission

I'm not seeing the link between that and $\sqrt{n}\leq\sum\frac{1}{\sqrt{r}}$ .

Paradoxica said:
(proof)

Thanks! Why do you go from $\geq$ to $>$ though? Also, how did you know to use that inequality you proved initially?

InteGrand · Oct 3, 2015

InteGrand · Oct 3, 2015

rand_althor said:
I'm not seeing the link between that and $\sqrt{n}\leq\sum\frac{1}{\sqrt{r}}$ .

The hint is that the integral of 1/root(x) is very similar to root(x). Riemann sums are often useful proving inequalities like this.

Paradoxica · Oct 3, 2015

rand_althor said:
I'm not seeing the link between that and $\sqrt{n}\leq\sum\frac{1}{\sqrt{r}}$ .

Thanks! Why do you go from $\geq$ to $>$ though? Also, how did you know to use that inequality you proved initially?

Lol I didn't. I retroactively inserted the proof for the inequality to make it look cleaner. The inequality case is basically the same as the equality case if you ignore $n=1$

rand_althor · Oct 3, 2015

InteGrand said:
The hint is that the integral of 1/root(x) is very similar to root(x). Riemann sums are often useful proving inequalities like this.

I can't get the LHS inequality. I can now see that with the RHS you show that approximating the area under the graph with rectangles gives an area that is lower than the exact integral, but with the LHS I'm still not sure. Could you explain what you mean by your hint?

Drsoccerball · Oct 3, 2015

Paradoxica said:
$\text{Wouldn't that be a strict inequality?}$

Yes it will be. But since testing n=1 reveals that they are equal we can confidently introduce an equality sign.

Drsoccerball · Oct 3, 2015

rand_althor said:
I'm not seeing the link between that and $\sqrt{n}\leq\sum\frac{1}{\sqrt{r}}$ .

I was talking about the RHS.

InteGrand · Oct 3, 2015

Paradoxica said:
$\text{Wouldn't that be a strict inequality?}$

Equality case occurs iff n = 1, and geometrically this is the case where we have 0 area (0-width interval), so the "approximation" is equal to the actual area.

InteGrand · Oct 3, 2015

rand_althor said:
I can't get the LHS inequality. I can now see that with the RHS you show that approximating the area under the graph with rectangles gives an area that is lower than the exact integral, but with the LHS I'm still not sure. Could you explain what you mean by your hint?

Basically, summation and integration are very similar (of course they are, due to how we define integration). So summing (x^r)'s from x = 1 to N or something will have bounds related the form N^{r+1} (can show using area arguments with Riemann sums), except when r = -1, in which case the bounds turn out to of the form ln(N) (expected, as integrating x^(-1) gives log).

Similarities between integration and summation can further be seen in the formulas for $\sum_{k=1}^N k^r$ , where r is a positive integer, are (r+1)-degree 'polynomials' in N (e.g. when r = 1, $\sum_{k=1}^N k^r = \sum_{k=1}^N k = \frac{N(N+1)}{2}$ , and you can see further examples here: https://en.wikipedia.org/wiki/Faulhaber's_formula#Examples (these area called Faulhaber formulas))

Paradoxica · Oct 3, 2015

Proof by induction for the RH Inequality.
$\text{Before we begin, we will prove a helpful inequality.}$
$\text{For } k>0, 4k^2 + 4k + 1>4k^2 + 4k$
$\Rightarrow 2\sqrt{k^2 + k}<2k+1$
$\text{Now we can begin.}$
$\text{Claim}: \sum_{r=1}^{n}{\frac{1}{\sqrt{r}}}\leq 2\sqrt{n} -1 \text{ for all } n \in \mathbb{Z}^+$
$\text{Base cases}: n=1 \text{ is equality}, n=2 \text{ is inequality.}$
$\text{Assume true for } n=k, \text{ and show this implies } k+1.$
$\text{for } n=k+1, \sum_{r=1}^{k+1}{\frac{1}{\sqrt{r}}}<2\sqrt{k}-1+\frac{1}{\sqrt{k+1}}$
$\text{Picking up our first proven inequality, } 2\sqrt{k^2 + k}+1<2(k+1)$
$\text{Dividing throughout by }\sqrt{k+1}, 2\sqrt{k} + \frac{1}{\sqrt{k+1}} < 2\sqrt{k+1}$
$\Rightarrow 2\sqrt{k} -1 + \frac{1}{\sqrt{k+1}} < 2\sqrt{k+1} -1$
$\noindent \text{From this, we conclude the inductive step, and out claim is true for } k+1,\text{ iff it is true for }k.$
$\noindent \text{Since it is true for }n=2,\text{ by the principle of induction, it is true for all }n \in \mathbb{Z}^+$
The code is correct, but it's not rendering....

rand_althor · Oct 3, 2015

Paradoxica said:
(proof)

Just so we can see what you wrote while Codecogs isn't working:

Thanks for the help!

Induction Question (1 Viewer)

Active Member

Well-Known Member

Active Member

-insert title here-

Well-Known Member

Well-Known Member

Active Member

Well-Known Member

-insert title here-

Active Member

Well-Known Member

Well-Known Member

-insert title here-

Active Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

-insert title here-

Active Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)