6
$\begingroup$

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)$.

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

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 $$

$\endgroup$
  • $\begingroup$ I think the first inequality goes the other way: Bernoulli says that $(1+x)^n \ge 1+nx$. $\endgroup$ – marty cohen Jul 8 '13 at 20:40
  • $\begingroup$ @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)$. $\endgroup$ – N. S. Jul 8 '13 at 22:05
  • $\begingroup$ 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)$? $\endgroup$ – marty cohen Jul 8 '13 at 23:33
  • $\begingroup$ @martycohen Ty, fixed that. $\endgroup$ – N. S. Jul 9 '13 at 1:05
7
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Andrés E. Caicedo Jul 8 '13 at 18:08
  • $\begingroup$ Doesn't "eventually positive" part have something to do with limits? $\endgroup$ – Constantine Jul 8 '13 at 19:39
  • $\begingroup$ I'll accept this if you give an explicit formula for $K$. $\endgroup$ – marty cohen Jul 8 '13 at 20:45
  • $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Jul 8 '13 at 20:58
  • $\begingroup$ The asymptotic growth of the Stirling numbers is a delicate topic, but some details are here. $\endgroup$ – Andrés E. Caicedo Jul 8 '13 at 20:59
4
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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)! $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.