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.
Best Answer
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}$?