Welcome to our community

Be a part of something great, join today!

Prove a_n ~ 2/3 n^(3/2)

Alexmahone

Active member
Jan 26, 2012
268
Let $a_n=\sqrt{1}+\sqrt{2}+\ldots+\sqrt{n}$. Prove $a_n\sim\frac{2}{3}n^{3/2}$; ie, the ratio has limit 1 as $n\to\infty$.

I have posted my unsuccessful attempt to use the squeeze theorem. How do I improve the upper bound?

View attachment 9
 
Last edited:

ThePerfectHacker

Well-known member
Jan 26, 2012
236
Hello,

1) Draw the graph of the function $f(x) = \sqrt{x}$ on the interval $[0,n]$.
2) Partition $[0,n]$ into $n$ sub-intervals: $[0,1], [1,2], ... , [n-1,n]$.
3) Form the Riemann sum where the sample point is chosen as the left-endpoint in each subinterval.
4) Form the Riemann sum where the sample point is chosen as the right-endpoint in each subinterval.
5) Observe that #3 is less than the area below $\sqrt{x}$ on $[0,n]$.
6) Observe that #4 is greater than the area below $\sqrt{x}$ on $[0,n]$.

Putting all of this together we get that,
$$ \sqrt{1} + \sqrt{2} + ... + \sqrt{n-1} < \int_0^n \sqrt{x} ~ dx < \sqrt{2} + \sqrt{3} + ... + \sqrt{n} $$
Thus,
$$ \tfrac{2}{3}n^{3/2} + 1 < \sqrt{1} + \sqrt{2} + ... + \sqrt{n} < \tfrac{2}{3}n^{3/2} + \sqrt{n}$$

Can you finish these steps yourself?

Bonus Problem: Show that $1^k + 2^k + 3^k + ... + n^k = \frac{n^{k+1}}{k+1} + \varepsilon(n)$ where $|\varepsilon(n)| < Mn^k$ where $M$ is some constant.
(Note, this is a generalization of your problem. Here $k$ is an positive real number).
 

Alexmahone

Active member
Jan 26, 2012
268
Thanks for your help, but is there any way to salvage my attempt, say by using a smaller rectangle for the upper bound.
 

ThePerfectHacker

Well-known member
Jan 26, 2012
236
Thanks for your help, but is there any way to salvage my attempt, say by using a smaller rectangle for the upper bound.
Based on your work you have shown that,
$$ \frac{2}{3} n^{3/2} < \sqrt{1} + \sqrt{2} + ... + \sqrt{n} < n^{3/2} $$
If you divide it out you get,
$$ \frac{2}{3} < \frac{\sqrt{1} + \sqrt{2} + ... + \sqrt{n}}{ n^{3/2} } < 1 $$
Here you cannot use any squeeze theorem as the lower and upper bounds have different limits. In other to apply squeeze theorem you need to have both the limits be equal.
 

PaulRS

Member
Jan 26, 2012
37
Another way:

Let $\left \lfloor x \right \rfloor$ denote the greatest integer that is less or equal than $x$ (the integer satisfying $\left \lfloor x \right \rfloor \leq x < \left \lfloor x \right \rfloor + 1$ ).

Note that $ \displaystyle\sum_{k=1}^{n}{\sqrt{k}} = \sum_{k=1}^{n}{\left\lfloor\sqrt{k}\right\rfloor} + R(n)$ where $| R(n) | \leq n$ , hence the remainder $R(n)$ is not going to be "big" enough to modify the asymptotic result we are looking for. $(*)$

The key observation is that $\left\lfloor\sqrt{k}\right\rfloor$ is constant when $k\in\{m^2,...,(m+1)^2-1\}$ and is equal to $m$ there (i.e. it is constants in large intervals)

Thus we write: $\sum_{k=1}^{n}{\left\lfloor\sqrt{k}\right\rfloor} = \sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor - 1}{m \cdot \left( (m+1)^2 - m^2 \right)} + \left\lfloor\sqrt{n}\right\rfloor \cdot \left( n - \left\lfloor\sqrt{n}\right\rfloor^2 + 1\right) $ $(**)$

Now: $\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor - 1}{m \cdot \left( (m+1)^2 - m^2 \right)} = \sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor - 1}{m \cdot \left( 2\cdot m + 1 \right)} = 2 \cdot \sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor - 1}m^2 + \sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor - 1}m $

Since $\sum_{m=1}^a m^2 = \frac{a \cdot (a + 1) \cdot (2\cdot a + 1)}{ 6 } \sim \frac{a^3}{3}$ and $\sum_{m=1}^a m = \frac{a \cdot (a + 1) }{ 2 } \sim \frac{a^2}{2}$ we find: $ \sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor - 1}{m \cdot \left( (m+1)^2 - m^2 \right)} \sim \frac{2}{3} \cdot (\left\lfloor\sqrt{n}\right\rfloor - 1)^3 \sim \frac{2}{3} \cdot n^{3/2} $ $(***)$

Finally we note that: $\left\lfloor\sqrt{n}\right\rfloor \leq \sqrt{n} < \left\lfloor\sqrt{n}\right\rfloor + 1$ implies $\left\lfloor\sqrt{n}\right\rfloor^2 \leq n < (\left\lfloor\sqrt{n}\right\rfloor + 1)^2$ and so $ 0 \leq n - \left\lfloor\sqrt{n}\right\rfloor^2 < (\left\lfloor\sqrt{n}\right\rfloor + 1)^2 - \left\lfloor\sqrt{n}\right\rfloor^2 = 2\cdot \left\lfloor\sqrt{n}\right\rfloor + 1$ thus $ \left\lfloor\sqrt{n}\right\rfloor \cdot \left( n - \left\lfloor\sqrt{n}\right\rfloor^2 + 1\right) \sim 2 \cdot n$ $(****)$

Now $(*)$, $(**)$ , $(***)$ and $(****)$ put together imply the result.
 

CaptainBlack

Well-known member
Jan 26, 2012
890
Thanks for your help, but is there any way to salvage my attempt, say by using a smaller rectangle for the upper bound.
IPH's method does exactly this. He uses your lower limit on the sum but replaces your upper limit by a tighter limit based on the same idea you have used for your lower limit.

(At least when he corrects his mistakes :) )

An improved upper limit is \( \displaystyle \int_1^{n+1} \sqrt{x} \; dx \)



CB
 
Last edited:

CaptainBlack

Well-known member
Jan 26, 2012
890
Thus,
$$ \tfrac{2}{3}n^{3/2} + 1 < \sqrt{1} + \sqrt{2} + ... + \sqrt{n} < \tfrac{2}{3}n^{3/2} + \sqrt{n}$$
Except put \(n=3\) then this is a claim that:

\[ \tfrac{2}{3}3^{3/2}+1=4.4641.. < \sqrt{1} + \sqrt{2} + \sqrt{3}=4.14626... \]

CB
 
Last edited: