T - Improving Upper Bound for $a_n$ in Series for $n$

[alexmahone]

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?

https://www.physicsforums.com/attachments/9

 

[ThePerfectHacker]

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]

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

 

[ThePerfectHacker]

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]

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]

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

 

[CaptainBlack]

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