1

Suppose $ k $ is a positive integer. Prove that there is some positive integer $ a $ such that for all $ n>a, 2^n \geq n^k $. Hint use divisor algorithm.

From this book http://users.metu.edu.tr/serge/courses/111-2011/textbook-math111.pdf page 298 q 14. Answer also in that book but I don't fully understand it. If anyone care to give a more thorough explanation that would be helpful. Also alternate solutions are welcome.

helios123
  • 63

2 Answers2

0

Let $b\ge \frac{1}{\sqrt[k]{2}-1}$ and assume that $2^b\geq b^k$. Then note that $(1+\frac1b)^k\ge2$, and so

\begin{align} (b+1)^k&=\frac{(b+1)^k}{b^k}b^k\\ &\le\left(\frac{b+1}{b}\right)^k2^b\\ &=\left(1+\frac{1}{b}\right)^k2^b\\ &\le 2\cdot2^b\\ &\le 2^{b+1}\\ \end{align} This means, once we have $n>\frac1{\sqrt[k]{2}-1}$ such that $2^n\ge n^k$, the expression will remain true for all $n$ by induction.

Now we're to find an $a$ satisfying

For all $n>a$, we have $2^n\ge n^k$.

Let's try $a=2^k$. It is clear that $2^k\ge k^2$, so that we see

$$2^a=2^{2^k}\ge 2^{k^2}=(2^k)^k=a^k$$

The expression is thus true for $a=2^k$. With our induction above, this means it should hold for all $n>a$, but we used $n\geq \frac{1}{\sqrt[k]{2}-1}$ in our induction; thus, we can choose $a=\max\{2^k,\frac{1}{\sqrt[k]{2}-1}\}$ (which you can even prove to be $2^k$, but that's irrelevent here).

  • Sorry I don't understand from this point "Now note..." especially the 2^k greater than or equal to k^k, how do you derive this is true? – helios123 May 04 '17 at 13:04
  • I made a mistake, obviously, $2^k\le k^k$ whenver $2\le k$. I've rewritten a part of my answer, I hope this clears things up –  May 04 '17 at 20:41
0

Alternate method: Let $a= (k+1)!2^k.$ For $n>a,$ in the binomial expansion $$2^{n+k}=(1+1)^{n+k}=\sum_{i=0}^{n+k}\binom {n+k}{i}$$ all the terms in the summation are positive.

So take the term with $i=k+1,$ and we have $$2^n2^k=2^{n+k}>\binom {n+k}{k+1}=\frac {1}{(k+1)!}\prod_{j=0}^{k}((n+k+1)-j).$$ Now for $0\leq j\leq k$ we have $(n+k+1)-j=n+(k+1-j)>n.$ Therefore $$2^n2^k=2^{n+k}>\binom {n+k}{k+1}> \frac {1}{(k+1)!}\prod_{j=0}^{k}n=$$ $$=\frac {n^{k+1}}{(k+1)!}=n\cdot \frac {n^k}{(k+1)!}>a\cdot \frac {n^k}{(k+1)!}=$$ $$= (k+1)!2^k\cdot \frac {n^k}{(k+1)!}= n^k2^k.$$ So we have $2^n2^k>n^k2^k,$ so $2^n>n^k$.

Remark:The idea is that $p(n)=\binom {n+k}{k+1}$ is a polynomial of degree $k+1$ in $n$ when $n\geq k,$ with positive leading co-efficient $A_{k+1},$ so $p(n)$ will be greater than $(2n)^k$ for all sufficiently large $n.$ Because if $p(n)=\sum_{j=0}^{k+1}n^jA_j$ then $p(n)/(2n)^k=nA_{k+1}2^{-k}+\sum_{j=0}^k(2n)^{-(k-j)}A_j,$ and $0<(2n)^{-(k-j)}\leq 1$ for $0\leq j\leq k.$

DanielWainfleet
  • 57,985