1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Exponential grows faster than polynomial
  1. On polynomials (Replies: 7)

Loading...