Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Exponential grows faster than polynomial

  1. Dec 18, 2011 #1
    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].
     
    Last edited: Dec 18, 2011
  2. jcsd
  3. Dec 19, 2011 #2
    So you needd to prove

    [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...
     
  4. Dec 19, 2011 #3
    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}{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} [/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].
     
    Last edited: Dec 19, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook