Inductive question

Question

Asked to prove that for $n \in \mathbb{Z^+}$:

$\sqrt{1}+\sqrt{2}+...+\sqrt{n}\ge\frac{2}{3}n\sqrt{n}$ by mathematical induction.

My inductive hypothesis is then:

$\sqrt{1}+\sqrt{2}+...+\sqrt{k}\ge\frac{2}{3}k\sqrt{k}$

I've come to this step:

$\sqrt{1}+\sqrt{2}+...+\sqrt{k}+\sqrt{k+1}\ge\frac{2}{3}k\sqrt{k}+\sqrt{k+1}$

I know that I want the RHS to read $\frac{2}{3}k\sqrt{k+1}+\frac{2}{3}\sqrt{k+1}$ but I'm not sure how to get from the last line to this line while ensuring the inequality still holds ... What am I missing?

Answer 1

I just propose an other solution :

If $f:[0,1]\to \mathbb R$ is increasing, and if $0=x_0<x_1<...<x_n=1$, then $$\sum_{k=0}^{n-1}(x_{k+1}-x_k)f(x_k)\leq \int_0^1 f\leq \sum_{k=0}^{n-1}(x_{k+1}-x_k)f(x_{k+1}).$$

Since $x\mapsto \sqrt x$ is increasing on $[0,1]$, taking $x_k=\frac{k}{n}$, $k=0,...,n$ you therefore have

$$\frac{1}{n}\sum_{k=1}^n\sqrt{\frac{k}{n}}=\frac{1}{n}\sum_{k=0}^{n-1}\sqrt{\frac{k+1}{n}}\geq \int_0^1\sqrt x\,\mathrm d x=\left[\frac{2}{3}x^{\frac{3}{2}}\right]_{0}^1=\frac{2}{3}.$$

The claim follow.

Answer 2

You don't want the RHS to read $\frac23k\sqrt{k+1} + \sqrt{k+1}$. you want it to read $\frac23 k\sqrt{k+1} + \frac23\sqrt{k+1}$. Well, that is, at least, one option.

Or, more specifically, we want to show that $$ \frac23k\sqrt k + \sqrt{k+1} \geq \frac23(k+1)\sqrt{k+1}\\ \frac23k\sqrt k\geq \frac23(k+1)\sqrt{k+1} - \sqrt{k+1} $$ The LHS is positive. If the RHS is negative we're done. If not, we can square fearlessly. Squaring gives $$ \frac49k^3\geq \frac49(k+1)^3 - \frac43(k+1)^2 + k+1\\ k^3\geq k^3+3k^2+3k+1 - 3k^2-6k-1+k+1\\ 0\geq 1-2k $$ which is clearly true for any positive integer $k$.