# Prove via mathematical induction that $4n < 2^n$ for all $n≥5$.

I did the following base case $n = 5$ \begin{align*} 4(5) &\lt 2 ^5\\ 20 &\lt 32 \end{align*} So true.

\begin{align*} 4n &\lt 2^n\\ n &\lt 2^{n-2}\\ \log_2(n)+2 &\lt n \end{align*} But I don't think this is right. Where do I add in the $(n+1)$.

-
Do you really mean "for all $n\lt 5$"? That would require you to check four cases, which does not require induction. Did you mean "for all $n\geq 5$" instead? –  Arturo Magidin Apr 12 '12 at 20:42
yes thats what i meant n≥5 –  user1084113 Apr 12 '12 at 20:43

The induction base is correct.

For the inductive step, we assume that the result holds for $n$, with $n\geq 5$; that is, are assuming that $$4n\lt 2^n,\qquad n\geq 5.$$ We want to prove that, under this assumption, $4(n+1)\lt 2^{n+1}$.

Hint the first. $4(n+1) = 4n+4 \lt 2^n+4$, with the last step using the induction hypothesis.

Hint the second. $2^{n+1} = 2\times 2^n = 2^n+2^n$.

-

If $4n<2^n$ then $4n+4<2^n+4<2^n+2^n=2^{n+1}$ (the second inequality hold since $2^n\geq4$ for $n\geq 2$). It follows that $4(n+1)<2^{n+1}$.

-