# Prove the inequality for all natural numbers n using induction

$\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.

• No. To prove the claim by induction you have to show $\log_2 (k+1) < k+1$. – Isomorphism Sep 24 '15 at 19:57
• It might be helpful to rephrase the problem as $n < 2^n$. – jwsiegel Sep 24 '15 at 20:19
• Do you have to use induction? It is fairly straightforward that $\log_2n<\log_22^n=n$. – barak manos Sep 24 '15 at 20:22

$\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$

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$$

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

• I don't see how this should help in an induction proof? – supinf Sep 24 '15 at 20:44
• – Rob Arthan Sep 24 '15 at 21:31