Induction to prove that $\log_2 2^k \leq 2^{k/2}$ Prove by induction that for every $k\geq4,$ $\log_2(2^k)\leq 2^{k/2}$.
Then prove that $\log_2n\leq\sqrt{2n}$ for all n>=1 by using $\log_2 n$ is at most  $\log_2(2^k)$ for the smallest integer k such that $ n<=2^k$.
I tried the first part by induction: $\log_2(2^k)\leq 2^{k/2}$.
Base case: k=4,  $\log_2(2^4)\leq2^{4/2}$ gives $4\leq4,$ which is true.
Induction Hypothesis: Assume true for (k-1):  $\log_2(2^{(k-1)})\leq 2^{(k-1)/2}$
Inductions Step: Show that it is true for k: $\log_2(2^k)\leq 2^{k/2}$
At this step, I tried to make the inequality look like the one in the inductive hypothesis: $\log_2(2^{(k-1)}2^1)\leq 2^{k/2}$, which reduces to  $\log_2(2^{k-1})+1\leq2^{k/2}$. Then we can write it like this: $\log_2(2^{k-1})\leq2^{k/2}-1$. I am stuck here.

$\log_2 2^k = \log_2 2\cdot 2^{k-1} = \log_2 2^{k-1} + \log_2 2=\log_2 2^{k-1} + 1\le 2^{\frac{k-1}2} +1$
Now $(2^{\frac{k-1}2} +1)^2 = 2^{k-1} + 2\cdot 2^{\frac{k-1}2} + 1=$
$2^{k-1} + 2^{\frac {k-1}2+1} + 1=2^{k-1}(1 + 2^{-\frac {k-1}2 + 1} + \frac 1{2^{k-1}})$
$k-1 \ge  4$ so $\frac 1{2^{k-1}} < \frac 14$.  And $-\frac {k-1}2 + 1\le -1$ so $2^{-\frac {k-1}2 + 1}\le \frac 12$. so
$1 + 2^{-\frac {k-1}2 + 1} + \frac 1{2^{k-1}} < 1 + \frac 12 + \frac 14 < 2$.
So $(2^{\frac{k-1}2} +1)^2 < 2^{k-1}\cdot 2 = 2^k$.
So $2^{\frac{k-1}2} +1 < (2^k)^{\frac 12} = 2^{\frac k2}$ an
$\log_2 2^k < 2^{\frac k2}$.
.....
Which seems like a lot of work just to avoid  pointing out $\log_2 2^k = k$ and this whole thing is equivalent to proving $k \le 2^{\frac k2}$ for $k\ge 4$.  Which is probably easier.
If $k-1 \le 2^{\frac {k-1}2}$ then
$(k-1)^2 \le 2^{k-1}$ and as $2k-1 > 0$ then
$k^2 < k^2 - 2k+1 =(k-1)^2 \le 2^{k-1} < 2^k$ so $k < 2^{\frac k2}$.
