# Prove that $n^k < 2^n$ for all large enough $n$

If $k\ge 2$ is an integer, prove by elementary means (no calculus or limits) that there is a $N(k)$ such that $n^k < 2^n$ for all integers $n \ge N(k)$. Give an explicit form for $N(k)$.

• Three votes to close as off topic?? – The Chaz 2.0 Jul 9 '13 at 1:15

By Bernoulli

$$\sqrt[2k]{2}^n \geq 1+n(\sqrt[2k]{2}-1) \,.$$

Pick an $N(K)$ so that

$$\sqrt{N(K)}(\sqrt[2k]{2}-1) > 1 \,.(*)$$

Then, for all $n > N(K)$ we have

$$\sqrt[2k]{2}^n \geq 1+n(\sqrt[2k]{2}-1) > \sqrt{n}\sqrt{N(K)}(\sqrt[2k]{2}-1) > \sqrt{n} \,.$$

The value we get for $N(K)$ from $(*)$ is:

$$N(K)=1+\left\lfloor \left( \frac{1}{\sqrt[2k]{2}-1} \right)^2 \right\rfloor$$

• I think the first inequality goes the other way: Bernoulli says that $(1+x)^n \ge 1+nx$. – marty cohen Jul 8 '13 at 20:40
• @martycohen Yes, that's exactly what I wrote: $\sqrt[2k]{2}^n =(1+\sqrt[2k]{2}-1)^n \geq 1+n(\sqrt[2k]{2}-1)$. Or, $x= (\sqrt[2k]{2}-1)$. – N. S. Jul 8 '13 at 22:05
• I see. Also, shouldn't the expression for $N(K)$ be squared, since (*) has $\sqrt{N(K)}$? Also$^2$, could you write a simpler expression for $N(K)$? – marty cohen Jul 8 '13 at 23:33
• @martycohen Ty, fixed that. – N. S. Jul 9 '13 at 1:05

Note that a polynomial with positive leading coefficient is eventually positive: If $$p(x)=a_0+\dots+a_nx^n$$ and $a_n>0$, then $p(x)>0$ for $x$ large enough. For example, we can write $p(x)=a_n[(c_0+\dots+c_{n-1}x^{n-1})+x^n]$, and note that $$|c_0+\dots+c_{n-1}x^{n-1}|\le |c_0|+\dots+|c_{n-1}|x^{n-1}\le x^n/2$$ as long as $K:=\max\{1,2n|c_i|\colon i<n\}<x$, so $\displaystyle |c_i|<\frac{x}{2n}$ for all $i$, and $x^k<x^n$ for all $k<n$. This means that $$|p(x)|\ge a_n(x^n-|c_0+\dots+c_{n-1}x^{n-1}|)\ge a_n(x^n-x^n/2)>0,$$ the inequality holding at least for $x>K$.

Now, for $n>0$, we have that $\displaystyle 2^n\ge\binom n{k+1}$ (since the left hand side counts all subsets of a set of $n$ elements, and the right hand side only counts those subsets of size exactly $k+1$), and the latter is a polynomial of degree $k+1$ and positive leading coefficient. This means (by the previous paragraph) that $\displaystyle \binom n{k+1}>n^k$ for $n$ large enough, as $\displaystyle \binom n{k+1}-n^k$ is a polynomial with positive leading coefficient. But then $2^n>n^k$, as we wanted.

The value of $K$ can be computed directly from the expansion of $\displaystyle \binom n{k+1}-n^k$.

• Yes, that's what I meant, the binomial coefficient, $\binom n{k+1}=\frac{n(n-1)\dots(n-k)}{(k+1)!}$, seen as a polynomial in $n$. – Andrés E. Caicedo Jul 8 '13 at 18:08
• Doesn't "eventually positive" part have something to do with limits? – Constantine Jul 8 '13 at 19:39
• I'll accept this if you give an explicit formula for $K$. – marty cohen Jul 8 '13 at 20:45
• We have $\binom n{k+1}-n^k=\sum_{i=0}^{k+1}a_i x^i$. Here, $a_{k+1}=1/(k+1)!$, and in general $a_i=s(k+1,i)/(k+1)!$, where the $s(k+1,i)$ are the Stirling numbers of the first kind, except for $a_k=s(k+1,k)/(k+1)! - 1$. Letting $c_i=s(k+1,i)$, except for $c_k=s(k+1,i)-(k+1)!$, we can take $K=\max\{1,2(k+1)|c_i|\colon i<k+1\}$. I expect this bound can be significantly lowered, though. – Andrés E. Caicedo Jul 8 '13 at 20:58
• The asymptotic growth of the Stirling numbers is a delicate topic, but some details are here. – Andrés E. Caicedo Jul 8 '13 at 20:59

Write the inequality as $n < 2^{n/k}$.

Suppose this is true for $n$. I want to find conditions such that this is also true for $n+1$.

By assumption, $n+1 = n(1+\frac1{n}) < 2^{n/k}(1+\frac1{n})$ and this is less than $2^{(n+1)/k}$ if $2^{n/k}(1+\frac1{n}) < 2^{(n+1)/k}$ or $2^{1/k} > 1+\frac1{n}$.

I showed in another solution (from $(1+\frac{x}{k})^k < \frac1{1-x}$ for $0 < x < 1$,with $x = \frac12$) that $2^{1/k} > 1+\frac1{2k}$, so, if $n \ge 2k$ and $2^n > n^k$, then $2^m > m^k$ for all $m \ge n$.

We now need to find an initial $n \ge 2k$ such that $2^n > n^k$.

Let's try $n = ak$ for some $a$. $2^{ak} > (ak)^k \iff 2^a > ak$. Almost, but not quite.

Let's try $n = k^2$. $2^{k^2} > (k^2)^k \iff 2^{k} > k^2$. This is easy by induction. $2^5 > 5^2$, and, if $2^k > k^2$ and $k \ge 5$, $$(k+1)^2 = k^2+2k+1 = k^2(1+\frac{2}{k}+\frac1{k^2}) < 2^k(1+\frac{2}{5}+\frac1{25}) < 2^k(2) = 2^{k+1}$$

So, by this nested induction, if $k \ge 5$, if $n \ge k^2$ (so that, certainly, $n \ge 2k$), $2^n > n^k$.

For $k = 2, 3,$ and $4$, respective values of $n \ge 2k$ such that $2^n > n^k$ are $5$ ($2^5 > 5^2$), $10$ ($2^{10} > 10^3$), and $17$ ($2^{17} = 131072> 17^4=83521$).

These values of $n$ happen to be $k^2+1$, so the final result is:

If $n$ and $k$ are integers and $k \ge 2$ and $n \ge k^2+1$, then $2^n > n^k$.

Pick $n > 2k$. Then, $$2^n > \binom{n}{k + 1} = \frac{n (n - 1) \cdot \ldots \cdot (n - k)}{(k+1)!} \geq \frac{n^{k + 1}}{2^{k+1} (k+1)!}$$ by a trivial combinatorial argument for the first inequality, and using $n - k > n/2$ in the second inequality. Therefore $2^n > n^k$ as soon as $$n > 2^{k + 1} (k + 1)!$$

• I'll accept it, even though your bound is quite large. – marty cohen Jul 8 '13 at 20:38
• It's possible to improve it significantly! I'll post a comment later. – blabler Jul 8 '13 at 21:09