Prove the inequality for all natural numbers n using induction

Question

$\log_2 n<n$

I know how to prove the base case Base Case $\log_2 1<1$ likewise assuming the inequality for n=k; $\log_2 k<k$

Then to prove by induction I show $\log_2 k<(k+1)$?

I know it's true since the domain is all real numbers i just cant figure out the next step to prove it.

Answer 1

$\log_2 (n) = \frac{\ln (n)}{\ln(2)}$, where $ln$ is the natural log i.e. with base $e$

You need to show, $\log_2(n) < n\implies \frac{\ln (n)}{\ln(2)} < n \implies \ln(n) <n\cdot\ln(2) \implies \ln(n) < \ln(2^n)$

Since $\log$ is an increasing function you can rephrase your question to $n < 2^n$ as suggested by @jwsiegel

That is easy to show by induction

n=1: $1<2^1$. True.

Induction Hypothesis: $n-1< 2^{n-1}$

for $n \geq 2$, $n \leq 2(n-1) < 2*2^{n-1} = 2^n$

Answer 2

Hint: $\log_2 (1) = 0$, $\log_2 (2n + 1) > \log_2 (2n) = \log_2(n) + 1$.

Answer 3

For $k>1$, we have $$k+1 < 2k,$$ hence, because $\log(x)$ is increasing $$\log_2(k+1)< \log_2(2k) = \log_2(k) + 1 < k +1 $$