Register to reply 
Exponential grows faster than polynomial 
Share this thread: 
#1
Dec1811, 05:12 PM

P: 2

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


#2
Dec1911, 01:41 PM

Mentor
P: 18,240

[tex]\frac{2^{k^2+1}}{k^2+1}>1[/tex] Maybe you can start of by proving that if k>3, that the function [tex]f(k)=\frac{2^{k^2+1}}{k^2+1}>1[/tex] is increasing?? So once you proved that [tex]f(k+1)>f(k)[/tex] You only need to show that f(4)>1... 


#3
Dec1911, 04:13 PM

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 [itex] 2^{k^{2} + 1} > (k^{2} + 1)^{k} [/itex] for all [itex] k \in \mathbb{N} [/itex]. We check the cases when [itex] k = 1 [/itex], [itex] 2 [/itex], [itex] 3 [/itex] or [itex] 4 [/itex] directly. [tex] \begin{array}{ccccc} k & 1 & 2 & 3 & 4 \\ \hline 2^{k^{2} + 1} & 4 & 32 & 1025 & 131072 \\ (k^{2} + 1)^{k} & 2 & 25 & 1000 & 83521 \end{array} [/tex] For [itex] k \geq 5 [/itex], we first prove that [itex] 2^{k} > k^{2} + 1 [/itex]. The case when [itex] k = 5 [/itex] holds because [tex] 2^{5} = 32 > 26 = 5^{2} + 1. [/tex] If [itex] 2^{k} > k^{2} + 1 [/itex] for some [itex] k \geq 5 [/itex], then we have that [tex] 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}. [/tex] By induction, this proves that [itex] 2^{k} > k^{2} + 1 [/itex] for all [itex] k \geq 5 [/itex]. Using this result, we have that [tex] 2^{k^{2} + 1} > 2^{k^{2}} > (k^{2} + 1)^{k} , \qquad \forall \, k \geq 5. [/tex] Thus, we have shown that [itex] 2^{k^{2} + 1} > (k^{2} + 1)^{k} [/itex] for all [itex] k \in \mathbb{N} [/itex]. We deal with the case when [itex] k = 1 [/itex] separately; namely, we want to show that [itex] 2^{n} > n [/itex] for all [itex] n \geq 2 [/itex]. The inequality holds when [itex] n = 2 [/itex] because [tex] 2^{2} = 4 > 2. [/tex] If [itex] 2^{n} > n [/itex] for some [itex] n \geq 2 [/itex], then [tex] 2^{n+1} = 2 \cdot 2^{n} > 2 n = n + n \geq n + 1. [/tex] By induction, this proves that [itex] 2^{n} > n [/itex] for all [itex] n \geq 2 [/itex]. For [itex] k \geq 2 [/itex], we first show that [itex] (1 + \frac{1}{n})^{k} < 2 [/itex] for all [itex] n \geq k^{2} + 1 [/itex]. Recall that [itex] (1 + \frac{1}{n})^{n} [/itex] is a monotone increasing sequence that converges to [itex] e [/itex]. Thus, for any [itex] k \geq 2 [/itex] and [itex] n \geq k^{2} + 1 [/itex], we have that [tex] \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. [/tex] We showed above that [itex] 2^{k^{2} + 1} > (k^{2} + 1)^{k} [/itex] for all [itex] k \in \mathbb{N} [/itex]. If [itex] k \geq 2 [/itex] and [itex] 2^{n} > n^{k} [/itex], then our previous result implies that [tex] 2^{n + 1} = 2 \cdot 2^{n} > 2 n^{k} > \left( 1 + \frac{1}{n} \right)^{k} \cdot n^{k} = (n + 1)^{k}. [/tex] By induction, this proves that [itex] 2^{n} > n^{k} [/itex] for all [itex] k \geq 2 [/itex] and [itex] n \geq k^{2} + 1 [/itex]. Having previously checked that [itex] 2^{n} > n [/itex] for all [itex] n \geq 2 [/itex], we can assert that for any [itex] k \in \mathbb{N} [/itex], [itex] 2^{n} > n^{k} [/itex] for [itex] n \geq k^{2} + 1 [/itex]. 


Register to reply 
Related Discussions  
Big Oh: showing that a polynomial grows faster than any log function.  Calculus & Beyond Homework  0  
Which grows faster as x> infinity? ln(x^2+4) or x5?  Calculus & Beyond Homework  5  
Which grows faster, (x4)^3 or...  Calculus & Beyond Homework  13  
Faster Polynomial Multiplication  Precalculus Mathematics Homework  4  
Which function grows faster?  General Math  3 