Proof by induction: $\log n < n$ for $n ≥ 1$.

Question

I was just wondering it is possible to prove this statement via mathematical induction? (I know you can do it via calculus but I want to specifically do it via induction). I have given it a go but am getting stuck at the proof for $n+1$ statement.

Thanks.

Answer 1

Hint: use the facts that $\ln(n+1) = \ln n + \ln\!\left(1+\frac{1}{n}\right)$, that $\ln$ is increasing and that $\ln 2 < 1$.

Answer 2

$$\ln(n+1)<\ln(en)=(\ln n)+1\stackrel{\text{inductive hypothesis}}<n+1$$

Answer 3

$\log n < n$ is equivalent to $n < e^n$.

Now take $x=e-1\ge 1$ and use Bernoulli's inequality: $e^n = (1+x)^n \ge 1+nx \ge 1+n > n$.

This same argument proves that $\log_b n < n$ for all $b\ge 2$.

Induction is used to prove Bernoulli's inequality.