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

#### Alexmahone

##### Active member
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
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
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
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
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
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
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: