# Induction proof of lower bound for $\sum \sqrt n$

I'm having some trouble proving the following statement using mathematical induction:

$$\frac{1}{2}n^{\frac{3}{2}} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} + \sqrt{4} + ... + \sqrt{n} ,\text{ (for all sufficiently large n)}$$

I'm sort of confused because $n^{\frac{3}{2}}$ = $n n^{\frac{1}{2}}$ which means that there are n of the largest possible root values on the left hand side while the right hand side has values like $\sqrt{1}$, $\sqrt{2}$, etc. As n grows sufficiently large wouldn't the left hand side outgrow the right hand side no matter what the constant multiple is? If I'm thinking about this correctly just let me know, if not, any help would be appreciated.

-
I don't think your intuition is right. You probably know that $1+...+n = n(n+1)/2$ is quadratic and $1+...+n^2 = n(n+1)(2n+1)/3$ is cubic – Cocopuffs Sep 5 '12 at 0:04
Don't forget the $1/2$! There are $n/2$ of the largest possible root values on the left, not $n$. – Antonio Vargas Sep 5 '12 at 0:04
Are you having any particular trouble with the induction step? – Antonio Vargas Sep 5 '12 at 0:10
Can you estimate the LHS difference $\frac 12 n^{3/2}- \frac 12 (n-1)^{3/2}$? If it is always less than $\sqrt n$ from some point, there's your induction step. (Hint: Calculus!) – Henning Makholm Sep 5 '12 at 0:14

You’re right that $$\sum_{k=1}^n\sqrt k\le n\cdot\sqrt n=n^{3/2}\;,$$ but you can’t infer from that that $\frac12n^{3/2}$ will eventually exceed $\sum_{k=1}^n\sqrt k$. Suppose that we divide everything through by $n$. Then the claimed inequality becomes

$$\frac12\sqrt n\le\frac1n\sum_{k=1}^n\sqrt k\tag{1}\;.$$

The righthand side of $(1)$ is just the arithmetic mean of the square roots $\sqrt 1,\sqrt 2,\dots\sqrt n$. You’ve observed (correctly) that this mean cannot be any bigger than $\sqrt n$, the largest of the $n$ numbers, but that doesn’t mean that it must eventually be smaller than half of the largest number. In fact, if you draw the graph of $y=\sqrt x$ you’ll see that it gets less and less steep as $x$ increases. When $n$ is large, therefore, most of the square roots in the list $\sqrt 1,\sqrt 2,\dots,\sqrt n$ are a lot closer to $\sqrt n$ than they are to $0$, and when you average them, the result is closer to $\sqrt n$ than to $0$. But that just means that it’s bigger than $\frac12\sqrt n$.

To prove the theorm by induction, you have to establish a starting point (‘base case’) and prove an induction step. For the induction step, suppose that you know for some $n$ that $$\frac12n^{3/2}\le\sum_{k=1}^n\sqrt k\tag{2}\;;$$ this is your induction hypothesis. You want to use it to show that $$\frac12(n+1)^{3/2}\le\sum_{k=1}^{n+1}\sqrt k\;.\tag{3}$$

To get from the righthand side of $(2)$ to the righthand side of $(3)$, we’ve obviously just added $\sqrt{n+1}$. If we knew that the lefthand side increased by at most $\sqrt{n+1}$, i.e., that

$$\frac12(n+1)^{3/2}\le\frac12n^{3/2}+\sqrt{n+1}\;,$$ we’d be in business: we’d have

$$\frac12(n+1)^{3/2}\le\frac12n^{3/2}+\sqrt{n+1}\le\sum_{k=1}^n\sqrt k+\sqrt{n+1}=\sum_{k=1}^{n+1}\sqrt k\;,$$

showing that $(2)$ does imply $(3)$.

So how can we show that

$$\frac12(n+1)^{3/2}\le\frac12n^{3/2}+\sqrt{n+1}\;?\tag{4}$$

Let’s tinker a bit. $(4)$ is equivalent to

$$(n+1)^{3/2}\le n^{3/2}+2\sqrt{n+1}\;,$$

which is equivalent to

$$(n+1)\sqrt{n+1}\le n\sqrt n+2\sqrt{n+1}\;.$$

This in turn is equivalent to

$$n\sqrt{n+1}+\sqrt{n+1}\le n\sqrt n+2\sqrt{n+1}\;,$$

which is equivalent to

$$n\sqrt{n+1}\le n\sqrt n+\sqrt{n+1}$$ and then to $$(n-1)\sqrt{n+1}\le n\sqrt n\;.\tag{5}$$

Everything in $(5)$ is non-negative, so $(5)$ is equivalent (for positive integers $n$) to the inequality that you get by squaring it,

$$(n-1)^2(n+1)\le n^3\;.\tag{6}$$

Can you show that $(6)$ is true for all positive integers? If so, working back through the chain of equivalent inequalities gives you $(4)$ for all positive integers and thereby shows that $(2)$ implies $(3)$ for all positive integers. To finish the induction, you just have to find a positive integer $n_0$ for which $(2)$ is true to conclude that $(2)$ is true for all integers $n\ge n_0$.

Added: This is the elementary way to approach the problem. If you’re a bit ingenious and know your calculus, you can prove the result without induction. The sum $\sum_{k=1}^n\sqrt k$ is an upper Riemann sum for $\int_0^n\sqrt x~dx$, so $\int_0^n\sqrt x~dx\le\sum_{k=1}^n\sqrt k$. How does $\int_0^n\sqrt x~dx$ compare with $\frac12 n^{3/2}$?

-
Thanks this really helped, I believe I can finish the problem from here, but may take some time to really understand everything thoroughly. – Math_Illiterate Sep 5 '12 at 0:49
There is also a pre-calculus way to do this without induction: multiply both sides by $2$ and use the fact that $\sqrt{i}+\sqrt{n-i} \ge \sqrt{n}$ (easy by squaring both sides) to show that the RHS is $\ge (n+1)\sqrt{n}$ – Erick Wong Sep 5 '12 at 1:06