Exponential grows faster than polynomial

[koroviev]

Homework Statement

If $k$ is a natural number, prove that $2^{n} > n^{k}$ for all $n \geq k^{2} + 1$.

Homework Equations

We need to use a proof by induction.

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

 

[micromass]

Homework Statement

If $k$ is a natural number, prove that $2^{n} > n^{k}$ for all $n \geq k^{2} + 1$.

Homework Equations

We need to use a proof by induction.

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

 

[koroviev]

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