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.
 A: For the induction step, using Viktor Glombik's question comment hint that $\log_2(2^k) = k$, plus using $k$ instead of $k - 1$ for the induction step, note that instead of using that the left side increases by $1$, I'm going to use the multiplication increase  (since the right side increases by a multiplicative factor) to get
$$\begin{equation}\begin{aligned}
k & \le 2^{k/2} \\
k\left(\frac{k + 1}{k}\right) & \le 2^{k/2}\left(\frac{k + 1}{k}\right) \\
k + 1 & \le 2^{k/2}\left(\frac{k + 1}{k}\right)
\end{aligned}\end{equation}\tag{1}\label{eq1A}$$
Next, let
$$f(x) = \sqrt{2} - \frac{x + 1}{x} = (\sqrt{2} - 1) - \frac{1}{x} \tag{2}\label{eq2A}$$
This gives $f(4) = (\sqrt{2} - 1) - \frac{1}{4} \approx 0.1642$. Also, $f'(x) = \frac{1}{x^2} \gt 0$, which means $f(x)$ is a strictly increasing function for $x \ge 4$, so it's always positive then, i.e., $\sqrt{2} - \frac{x + 1}{x} \gt 0 \implies \sqrt{2} \gt \frac{x + 1}{x}$. Thus, for $k \ge 4$, this gives
$$2^{1/2} \gt \frac{k + 1}{k} \implies 2^{(k+1)/2} \gt 2^{k/2}\left(\frac{k + 1}{k}\right) \tag{3}\label{eq3A}$$
Using this in \eqref{eq1A} gives
$$k + 1 \lt 2^{(k+1)/2} \tag{4}\label{eq4A}$$
which completes the induction step.
I'll leave it to you to prove your second part, i.e., $\log_2(n) \le \sqrt{2n}$ for all $n \ge 1$.
A: I would first use the property that
$\displaystyle \log_2(2^{k}) = k$
So we have to show that
$\displaystyle k\leqslant \sqrt{2^{k}}$
Base step: P(4) $\displaystyle 4\leqslant \sqrt{2^{4}} =2^{2} =4$ (True)
Inductive step: Suppose that $\displaystyle k\leqslant \sqrt{2^{k}}$ is true for k (Inductive hypothesis)
For P(k+1) we have to show that:
$\displaystyle k+1\leqslant \sqrt{2^{k+1}}$
Let's start by considering
$\displaystyle k+1\leqslant \sqrt{2^{k}} +1$ from inductive hypothesis
Now we show that really:
$\displaystyle k+1\leqslant \sqrt{2^{k}} +1\leqslant \sqrt{2^{k+1}}$
We know that $\displaystyle \sqrt{2^{k+1}} =\sqrt{2}\sqrt{2^{k}}$
Let's substitute $\displaystyle \sqrt{2^{k}} =x$
We have to show that
$\displaystyle  \begin{array}{{>{\displaystyle}l}}
x+1\leqslant \sqrt{2} \ x\\
\sqrt{2} \ x\ -x\ \geqslant 1\\
\left(\sqrt{2} -1\right) x\geqslant 1\\
x\geqslant \frac{1}{\sqrt{2} -1} \approx 2.4\\
\sqrt{2^{k}} \geqslant 2.4\ ( True)
\end{array}$
because for $\displaystyle k\geqslant 4\ ,\ \sqrt{2^{k}} \geqslant 4 >2.4$
So this means that
$\displaystyle k+1\leqslant \sqrt{2^{k+1}}$
A: $\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}$.
