Sometimes the trick is to write the problem in a different form.
The inequality is equivalent to
$$\left(1+\frac{1}{n}\right)^n < n$$
The inductive step follows this way:
$$ \left(1+\frac{1}{n+1}\right)^{n+1} < \left(1+\frac{1}{n}\right)^{n+1}= \left(1+\frac{1}{n}\right)^{n}\left(1+\frac{1}{n}\right)$$
Use P(n) and you are done....
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}$?
Best Answer
You assume that $2^k+1\le 3^k$. Then you want to prove that under this assumption, we will have that $2^{k+1}+1\le3^{k+1}$.
$$\begin{align}2^{k+1}+1&=(2\times2^k)+1\\ &=2(2^k+1)-1\\ &=(2^k+1)+(2^k+1)-1\\ &\le 3^k+3^k-1\\ &=3^{k+1}-1-3^k\\ &\le 3^{k+1}\end{align}$$