0
$\begingroup$

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

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.