Algebra #22
by sjaelee, Sep 24, 2011, 3:11 PM
Quote:
Determine
![\[ \left\lfloor 1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{1000000}}\right\rfloor. \]](//latex.artofproblemsolving.com/2/2/8/2280a78f0114ee09be88c236c3da59804f2e2452.png)
![\[ \left\lfloor 1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{1000000}}\right\rfloor. \]](http://latex.artofproblemsolving.com/2/2/8/2280a78f0114ee09be88c236c3da59804f2e2452.png)
We start by making bounds. We note that
![\[\sum_{k=1}^{n}\frac{1}{\sqrt{k}+\sqrt{k+1}}\]](http://latex.artofproblemsolving.com/e/9/c/e9c5e3906b74996921ce7c7a06d945a44ff31086.png)
telescopes as
![\[\sqrt{k+1}-\sqrt{k}\]](http://latex.artofproblemsolving.com/1/f/e/1fed15b1e843a77a5ecb77b6fa64cd27b9fbab7c.png)
and is very close to our original sum divided by two, slighly less.
Evaulauting, we have t (with

![\[\sqrt{1000001}-1\]](http://latex.artofproblemsolving.com/8/9/1/89193856d4b979f6f440f2c7cbe94ca28405f080.png)


Now, the lower bound. I once proved that
![\[ 1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}< 2\sqrt{n} \]](http://latex.artofproblemsolving.com/e/5/5/e552c53ccc194a32a06d4c6f029ca2dd899e2ef9.png)
Proof
Base Case: 
We have
, or
, which is true.
Inductive Case:
.
Assume the expression is true for
. Then we will show it is true
for
. We have
![\[1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}<2\sqrt{n}\]](//latex.artofproblemsolving.com/c/c/4/cc4dd8b5229a23964b86a38f1ca96085e61aab3e.png)
and we want to show
We see the first expression is simply adding
to both sides of the assumed case inequality. If we show that
, then
![\[2\sqrt{n+1}>2\sqrt{n}+\frac{1}{\sqrt{n+1}}>
1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n+1}}\]](//latex.artofproblemsolving.com/6/a/f/6af598e40b58904253a265b3b7bef3d738b0c878.png)
So showing this![\[2\sqrt{n+1}>2\sqrt{n}+\frac{1}{\sqrt{n+1}}\]](//latex.artofproblemsolving.com/8/7/6/876e9e895dedc670f8aaf75485068c5462ba1b65.png)
will make the inductive case true.
We start by multiplying both sides by
to get
and
. Subtracting one,
and
. Since both are positive as
is
positive, we can square to comaper their values.
and
. Thus,
![\[2\sqrt{n+1}>2\sqrt{n}+\frac{1}{\sqrt{n+1}}\]](//latex.artofproblemsolving.com/8/7/6/876e9e895dedc670f8aaf75485068c5462ba1b65.png)
and the inductive case is true.

We have


Inductive Case:

Assume the expression is true for

for

![\[1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}<2\sqrt{n}\]](http://latex.artofproblemsolving.com/c/c/4/cc4dd8b5229a23964b86a38f1ca96085e61aab3e.png)
and we want to show
\[1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n+1}} <2\sqrt{n+1}\]
We see the first expression is simply adding

to both sides of the assumed case inequality. If we show that

![\[2\sqrt{n+1}>2\sqrt{n}+\frac{1}{\sqrt{n+1}}>
1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n+1}}\]](http://latex.artofproblemsolving.com/6/a/f/6af598e40b58904253a265b3b7bef3d738b0c878.png)
So showing this
![\[2\sqrt{n+1}>2\sqrt{n}+\frac{1}{\sqrt{n+1}}\]](http://latex.artofproblemsolving.com/8/7/6/876e9e895dedc670f8aaf75485068c5462ba1b65.png)
will make the inductive case true.
We start by multiplying both sides by






positive, we can square to comaper their values.


![\[2\sqrt{n+1}>2\sqrt{n}+\frac{1}{\sqrt{n+1}}\]](http://latex.artofproblemsolving.com/8/7/6/876e9e895dedc670f8aaf75485068c5462ba1b65.png)
and the inductive case is true.
We can prove for postive integers

![\[ 1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}< 2\sqrt{n}-1 \]](http://latex.artofproblemsolving.com/6/c/2/6c256e62cb0146f8ca4de769ba42787f4ee3f4e5.png)
in the same way if we find a base case. Testing,

Note that




This post has been edited 4 times. Last edited by djmathman, Sep 24, 2011, 4:17 PM