Proving a seemingly simple inequality using induction.

Question

I encountered an exercise asking to prove the following inequality:

$4log_2(n) \leq n$ for all integers $n \geq 16$ strictly using induction.

I understand intuitively why the inequality holds and I've thought of alternative methods to prove it, but my challenge has been proving it with induction. It seems like I've tried all sorts of algebraic manipulations and tricks with logarithms, but nothing works.

Answer 1

Hint:

Clearly $4 \log_2 n = n$ for $n=16$.

Now compute $4 \log_2 (n+1)$ and subtract $4 \log_2 n$ (for $n\geq 16$) to see that this increment is less than $1$, which means that the right-hand side is always greater than the left-hand side... your goal.

Answer 2

Hint:

Note $4\log_{2}(n) = \log_{2}(n^4)$. Also, since $f(x) = 2^{x}$ is a strictly increasing function, by taking $2$ to the power of both sides of the inequality you get

$$\log_{2}(n^4) \le n \iff n^4 \le 2^n \tag{1}\label{eq1A}$$

I believe this alternate inequality should be easier to prove by induction.

Answer 3

If you want a more general, pretty close to best possible result, you can look at my answer here Prove that $n^k < 2^n$ for all large enough $n$ where I show that if $n$ and $k$ are integers and $k \ge 2$ and $n \ge k^2+1$, then $2^n > n^k$.

The proof uses a number of induction steps.

Answer 4

I assume you want to operate with the given inequality directly.

So, for the induction step $n\to n+1$ you may proceed as follows using the induction hypothesis (IH) $4\log_2(n) \leq n$ for an $n\geq 16$:

$$4\log_2(n+1) = 4 \log_2 \left(n\left(1+\frac 1n\right)\right) = 4 \log_2 n + 4 \log_2 \left(1+\frac 1n\right)$$ $$\stackrel{IH}{\leq} n + 4 \log_2 \left(1+\frac 1n\right)\stackrel{!}{\leq}n+1$$

So, it is enough to show that $4 \log_2 \left(1+\frac 1n\right) \leq 1 \Leftrightarrow \left(1+\frac 1n\right)^4 \leq 2$.

Since $\left(1+\frac 1n\right)^4$ is decreasing, it is enough to show that this inequality is satisfied for $n= 16$, which you can verify easily:

$$\left(1+\frac 1n\right)^4= 1+ \frac{4}{n}+\frac{6}{n^2}+\frac{4}{n^3}+\frac{1}{n^4}$$ $$<1+\frac{4+6+4+1}{n}=1+\frac{15}{n}\stackrel{n = 16}{<}2$$