Prove $2^n > n^k$ for all $n \geq k^2 + 1$

Question

I've managed to prove this for a few specific cases of $k$ (($k=3$, $n \geq 10$) and ($k=4$, $n \geq 17$)) with induction, but I just don't see how to generalize it for any $k$. Even double induction is proving difficult because I can't even seem to prove the base case.

Any help is appreciated.

Answer 1

Consider this function: $$ f(u)=u\log 2-k\log u,\quad f'(u)=\log 2-\frac{k}{u}. $$ If $u\geq \frac{k}{\log 2}$, then $f(u)$ is increasing. Since $k^2+1\geq 2k>\frac{k}{\log 2}$, for all $n\geq k^2+1$ we have: $$ f(n)\geq f(k^2+1). $$ Therefore if we prove that $f(k^2+1)>0$ the result is proved. Therefore we should prove only that $$ 2^{k^2+1}>(k^2+1)^k\implies 2^{k+\frac 1k}>k^2+1 \tag{1}. $$ But for $k\geq 5$, we have: $$ 2^k=(1+1)^k\geq \binom{k}0+\binom{k}1+\binom{k}2+\binom{k}{k-2}+\binom{k}{k-1}+\binom{k}{k}=k^2+k+2. $$ Since $2^{1/k}>1$, we have for $k\geq 5$: $$ 2^{k+\frac 1k}\geq k^2+k+2>k^2+1. $$ The proof follows by checking the inequality $(1)$ for $k=1,2,3,4$.

Answer 2

Note the inequality is trivial for $k=0$ so let's consider only $k>0$.

The base case is, of course, establishing $2^{k^2+1} \geq (k^2+1)^k$ for all $k$.

So it suffices to establish $$\frac{2^{(k+1)^2+1}}{2^{k^2+1}}\geq \frac{(k^2+2k+2)^{k+1}}{(k^2+1)^k}$$ for large enough $k$ and work the finite number of cases left explicitly. So we want to show $$ 2^{2k+1}\geq\left(1+\dfrac{2k+1}{k^2+1}\right)^k (k^2+2k+2) $$ and since $RHS<\left(1+\dfrac{3k}{k^2}\right)^k(5k^2)<5e^3k^2<135k^2$ it suffices to show $$ 2^{2k+1}\geq 135k^2 $$ which holds for $k\geq 6$. The cases $k=1,\dots,6$ are easily checked.

Now having got that base case, for the induction step we want $$ 2\geq\left(\frac{n+1}{n}\right)^k $$ for $n\geq k^2+1$, so it suffices to show $$ 2\geq\left(1+\frac{1}{k^2+1}\right)^k. $$ This is clearly true when you binomially expand RHS and use the (rather crude) bound $\binom{k}{r}(k^2+1)^{-r}\leq k^{-r}$.

Answer 3

Since you have proven the inequality for $k=3$ and $k=4$, and the cases $k=1$ and $k=2$ are easy, I shall deal with the remaining cases, namely, when $k\geq5$ is an integer. We shall assume that $k\geq 5$ unless otherwise stated.

First, it can be easily proven by induction that $$2^m>m^2$$ for all integers $m\geq 5$. Thus, we get $$2^{k^2}=\left(2^k\right)^k>\left(k^2\right)^k\,.$$ That is, $2^n>n^k$ when $n=k^2$. This provides the basis step for our proof of the inequality $$2^n>n^k\text{ for every integer }n\geq k^2\,.$$

For the inductive step, suppose that $n\geq k^2$ and $2^n>n^k$. Then, $$2^{n+1}>2\,n^k>(n+1)^k\,,$$ as $$\left(1+\frac{1}{n}\right)^k\leq \left(1+\frac{1}{k^2}\right)^k<\text{e}^{\frac{1}{k}}\leq \text{e}^{\frac{1}{5}}<2\,.$$ Here, $\text{e}\approx 2.718$ is the natural base of logarithm, and the famous inequality $$\left(1+\frac{1}{m}\right)^m<\text{e}\text{ for each positive integer }m$$ has been used.

Indeed, it follows that, for any nonnegative integer $k$ and for any integer $n\geq k^2$ with a single exception when $(k,n)=(3,9)$, we have $$2^n\geq n^k\,.$$ The inequality becomes an equality if and only if $(k,n)=(0,0)$, $(k,n)=(2,4)$, and $(k,n)=(4,16)$. Here, we use the convention that $0^0=1$. In fact, we can find a more appropriate lower bound than $n\geq k^2$. Let $W_s$ denote the $s$-th branch of the Lambert $W$-function. Then, for each integer $k\geq 2$, we have $$2^n\geq n^k\text{ for every integer }n\geq \left\lceil -\frac{k\,W_{-1}\left(-\frac{\ln(2)}{k}\right)}{\ln(2)}\right\rceil=:b_k\,.$$ We have $b_2=4$, $b_3=10$, $b_4=16$, $b_5=23$, and $b_6=30$. (We can additionally define $b_0:=0$ and $b_1:=0$.) Because $$W_{-1}(-\epsilon)\approx\ln(\epsilon)$$ for small $\epsilon>0$, we get that $$b_k\approx \frac{k\,\ln\left(\frac{k}{\ln(2)}\right)}{\ln(2)}\approx \frac{k\,\ln(k)}{\ln(2)}$$ for large values of $k$.