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.