$ 3 \sum^{n}_{k=1} \sqrt{k} \geq 2n \sqrt{n} + 1, n \in \mathbb{N} \setminus \{0\}$ Induction proof. How to separate multiplication. I have a problem with induction proofs like this one:
$$ 3 \sum^{n}_{k=1} \sqrt{k} \geq 2n \sqrt{n} + 1, n \in \mathbb{N} \setminus \{0\}$$
In the base case it works fine (for $n = 1$):
$$3 * \sqrt{1} \geq 2 + 1 \implies 3 = 3$$
Thesis ~ as above.
Now for $n + 1$:
$$ 3 \sum^{n+1}_{k=1} \sqrt{k} \geq 2(n+1) \sqrt{n+1} + 1$$
$$ 3 \sum^{n}_{k=1} \sqrt{k} + 3\sqrt{n+1} \geq 2n\sqrt{n+1} +1 + 2\sqrt{n+1}$$
And here is my problem: I don't know how to separate $1$ form $n$ in $2n\sqrt{n+1}$ on the left hand side.
On the right hand side of the inequality I got a sum which is good, but I can not separate that multiplication on the right. I thought about:

*

*using Bernoulis inequality, but then I "loose" the square root and can not use my induction thesis.

*changing $1$ under the square root for $1$ outside, but then the inequality doesn't work - right hand side is too big

*putting both sides of inequality in $e^{ln\{\}}$, but it doesn't work either

I don't know whot to do and it is not the first time I am having exactly the same problem in induction proofs. Can anybody help me?
 A: For the induction step, we have:
\begin{align}
3\sum_{k=1}^{n+1}\sqrt k &= 3\sum_{k=1}^{n}\sqrt k + 3\sqrt{n+1}\\
&\ge2n \sqrt n + 1 + 3\sqrt {n+1}\\
&=2(n+1)\sqrt{n+1}+1-2n(\sqrt{n+1}-\sqrt n)+\sqrt {n+1}\\
&=2(n+1)\sqrt{n+1}+1-\frac {2n}{\sqrt{n+1}+\sqrt n}+\sqrt {n+1}\\
&\ge 2(n+1)\sqrt{n+1}+1-\frac {2n}{2\sqrt n}+\sqrt {n+1}\\
&= 2(n+1)\sqrt{n+1}+1-\sqrt n+\sqrt {n+1}\\
&> 2(n+1)\sqrt{n+1}+1
\end{align}
A: Here is a careful derivation that outlines the reasoning process in induction proofs.
First, it's important to distinguish what you know to be true from what you want to be true. If the proposition holds for $n$, you know that
$$3\sum_{k=1}^n\sqrt k\ge 2n\sqrt n + 1\tag1$$
To show the proposition holds for $n+1$ you want to show
$$3\sum_{k=1}^{n+1}\sqrt k\ge 2(n+1)\sqrt {n+1} + 1\tag2$$
You are allowed to use (1) to get to (2). In anticipation of using (1), you write
$$3\sum_{k=1}^{n+1}\sqrt k = 3\sum_{k=1}^n\sqrt k + 3\sqrt{n+1}
$$
and then plug in (1):
$$3\sum_{k=1}^{n+1}\sqrt k \ge 2n\sqrt n + 1 + 3\sqrt{n+1}
$$
So what you want to be true is:
$$2n\sqrt n + 1 + 3\sqrt{n+1}\ge 2(n+1)\sqrt {n+1} + 1\tag3
$$
To verify this, the first step is to do algebra to simplify (3) into an equivalent but simpler statement. So get rid of the $2\sqrt{n+1} + 1$ that's common to both sides. This leaves the equivalent assertion, which still requires proof:
$$ 2n\sqrt n +\sqrt{n+1}\ge 2n\sqrt{n+1}\tag4$$
The other answers offer several ways to arrive at (4). Another approach is to rearrange into yet another equivalent statement (still requires proof), with $\sqrt n$ on one side and $\sqrt{n+1}$ on the other:
$$
2n\sqrt n\ge (2n-1)\sqrt{n+1}\tag5
$$
Now square both sides:
$$4n^3\ge (2n-1)^2(n+1)\tag6$$
Is (6) true? If so, then run the argument backwards from (6) to (3). If the reverse chain of implications is still valid, you are done. (Note that $n$ is at least $1$, so the step (5) $\to$ (6) is indeed reversible.)
A: Induction based proof:
Assume true for $n$. For $n + 1$, we have
\begin{align*}
\sqrt{n + 1} & \geq \sqrt{n} \\
\implies \sqrt{n + 1} & \geq \frac{2n}{\sqrt{n} + \sqrt{n+1}} \\
\implies \sqrt{n + 1} & \geq 2n(\sqrt{n+1} - \sqrt{n}) \\
\implies 2n \sqrt{n} + \sqrt{n + 1} & \geq 2n\sqrt{n+1}.
\end{align*}
Thus,
$ \displaystyle 2(n+1)\sqrt{n + 1} + 1 \leq 2n \sqrt{n} + 1 + 3\sqrt{n + 1} \leq 3\sum_{k = 1}^n \sqrt{k} + 3\sqrt{n + 1} \leq 3\sum_{k = 1}^{n+1} \sqrt{k}$, as required.
A: For many problems of this kind, once you prove the base case you only need to compare the increment from $n$ to $n+1$ on both sides,
$$3\sqrt{n+1} \ge 2((n+1)\sqrt{n+1}-n\sqrt n) \\
\iff 2n\sqrt{n} \ge (2n-1)\sqrt{n+1}\\
\iff 4n^3 \ge (2n-1)^2(n+1)=4n^3-3n+1\\
\iff 3n\ge 1$$
which is true.
One added benefit is this can be easily converted to a non-induction, telescopic proof.
