# Exponential grows faster than polynomial

by koroviev
Tags: exponential, induction, polynomial
 P: 2 1. The problem statement, all variables and given/known data If $k$ is a natural number, prove that $2^{n} > n^{k}$ for all $n \geq k^{2} + 1$. 2. Relevant equations We need to use a proof by induction. 3. The attempt at a solution Let's do the case when $k = 4$. We check the base case directly: $$2^{17} = 131072 > 83521 = 17^4$$ Suppose $2^{n} > n^{4}$ for some $n \geq 17$, we have that $$2^{n+1} = 2 \cdot 2^{n} > 2 n^{4} = n^{4} + n^{4}$$ Since $n \geq 5$, we have that $$2^{n+1} > n^{4} + 5 n^{3} = n^{4} + 4 n^{3} + n^{3}$$ Since $n \geq 7$, we have that $$2^{n+1} > n^{4} + 4 n^{3} + 7 n^{2} = n^{4} + 4 n^{3} + 6 n^{2} + n^{2}$$ Since $n \geq 5$, we have that $$2^{n+1} > n^{4} + 4 n^{3} + 6 n^{2} + 5 n = n^{4} + 4 n^{3} + 6 n^{2} + 4 n + n$$ Finally, since $n \geq 1$, we have that $$2^{n+1} > n^{4} + 4 n^{3} + 6 n^{2} + 4 n + 1 = (n + 1)^{4}$$ However, I cannot extend this method to a general $k$. First, I have trouble with the base case: $$2^{k^{2} + 1} > (k^{2} + 1)^{k}$$ I tried to do this by induction on $k$, but didn't make much headway. My method for the inductive case also breaks down because for $k \geq 8$ the largest coefficient in the expansion of $(n + 1)^{k}$ is larger than $k^{2} + 1$.
Emeritus
Thanks
PF Gold
P: 15,868
 Quote by koroviev 1. The problem statement, all variables and given/known data If $k$ is a natural number, prove that $2^{n} > n^{k}$ for all $n \geq k^{2} + 1$. 2. Relevant equations We need to use a proof by induction. 3. The attempt at a solution Let's do the case when $k = 4$. We check the base case directly: $$2^{17} = 131072 > 83521 = 17^4$$ Suppose $2^{n} > n^{4}$ for some $n \geq 17$, we have that $$2^{n+1} = 2 \cdot 2^{n} > 2 n^{4} = n^{4} + n^{4}$$ Since $n \geq 5$, we have that $$2^{n+1} > n^{4} + 5 n^{3} = n^{4} + 4 n^{3} + n^{3}$$ Since $n \geq 7$, we have that $$2^{n+1} > n^{4} + 4 n^{3} + 7 n^{2} = n^{4} + 4 n^{3} + 6 n^{2} + n^{2}$$ Since $n \geq 5$, we have that $$2^{n+1} > n^{4} + 4 n^{3} + 6 n^{2} + 5 n = n^{4} + 4 n^{3} + 6 n^{2} + 4 n + n$$ Finally, since $n \geq 1$, we have that $$2^{n+1} > n^{4} + 4 n^{3} + 6 n^{2} + 4 n + 1 = (n + 1)^{4}$$ However, I cannot extend this method to a general $k$. First, I have trouble with the base case: $$2^{k^{2} + 1} > (k^{2} + 1)^{k}$$ I tried to do this by induction on $k$, but didn't make much headway. My method for the inductive case also breaks down because for $k \geq 8$ the largest coefficient in the expansion of $(n + 1)^{k}$ is larger than $k^{2} + 1$.
So you needd to prove

$$\frac{2^{k^2+1}}{k^2+1}>1$$

Maybe you can start of by proving that if k>3, that the function

$$f(k)=\frac{2^{k^2+1}}{k^2+1}>1$$

is increasing?? So once you proved that

$$f(k+1)>f(k)$$

You only need to show that f(4)>1...
 P: 2 Thanks for the reply! (And sorry that I put in this wrong forum originally -- I got the problem from a computer science professor, but the problem is probably more math now that I think about it). I actually ended up solving the problem myself, though my methods probably aren't the most elegant or efficient possible. First, we show that $2^{k^{2} + 1} > (k^{2} + 1)^{k}$ for all $k \in \mathbb{N}$. We check the cases when $k = 1$, $2$, $3$ or $4$ directly. $$\begin{array}{c|cccc} k & 1 & 2 & 3 & 4 \\ \hline 2^{k^{2} + 1} & 4 & 32 & 1025 & 131072 \\ (k^{2} + 1)^{k} & 2 & 25 & 1000 & 83521 \end{array}$$ For $k \geq 5$, we first prove that $2^{k} > k^{2} + 1$. The case when $k = 5$ holds because $$2^{5} = 32 > 26 = 5^{2} + 1.$$ If $2^{k} > k^{2} + 1$ for some $k \geq 5$, then we have that $$2^{k + 1} = 2 \cdot 2^{k} > 2 \cdot (k^{2} + 1) = k^{2} + k^{2} + 2 \geq k^{2} + 2 k + 2 \geq k^{2} + 2 k + 1 = (k + 1)^{2}.$$ By induction, this proves that $2^{k} > k^{2} + 1$ for all $k \geq 5$. Using this result, we have that $$2^{k^{2} + 1} > 2^{k^{2}} > (k^{2} + 1)^{k} , \qquad \forall \, k \geq 5.$$ Thus, we have shown that $2^{k^{2} + 1} > (k^{2} + 1)^{k}$ for all $k \in \mathbb{N}$. We deal with the case when $k = 1$ separately; namely, we want to show that $2^{n} > n$ for all $n \geq 2$. The inequality holds when $n = 2$ because $$2^{2} = 4 > 2.$$ If $2^{n} > n$ for some $n \geq 2$, then $$2^{n+1} = 2 \cdot 2^{n} > 2 n = n + n \geq n + 1.$$ By induction, this proves that $2^{n} > n$ for all $n \geq 2$. For $k \geq 2$, we first show that $(1 + \frac{1}{n})^{k} < 2$ for all $n \geq k^{2} + 1$. Recall that $(1 + \frac{1}{n})^{n}$ is a monotone increasing sequence that converges to $e$. Thus, for any $k \geq 2$ and $n \geq k^{2} + 1$, we have that $$\left( 1 + \frac{1}{n} \right)^{k} = \left[ \left( 1 + \frac{1}{n} \right)^{n} \right]^{\frac{k}{n}} < e^{\frac{k}{n}} \leq e^{\frac{k}{k^{2}}} = e^{\frac{1}{k}} \leq e^{\frac{1}{2}} < 2.$$ We showed above that $2^{k^{2} + 1} > (k^{2} + 1)^{k}$ for all $k \in \mathbb{N}$. If $k \geq 2$ and $2^{n} > n^{k}$, then our previous result implies that $$2^{n + 1} = 2 \cdot 2^{n} > 2 n^{k} > \left( 1 + \frac{1}{n} \right)^{k} \cdot n^{k} = (n + 1)^{k}.$$ By induction, this proves that $2^{n} > n^{k}$ for all $k \geq 2$ and $n \geq k^{2} + 1$. Having previously checked that $2^{n} > n$ for all $n \geq 2$, we can assert that for any $k \in \mathbb{N}$, $2^{n} > n^{k}$ for $n \geq k^{2} + 1$.

 Related Discussions Calculus & Beyond Homework 0 Calculus & Beyond Homework 5 Calculus & Beyond Homework 13 Precalculus Mathematics Homework 4 General Math 3