Register to reply

Exponential grows faster than polynomial

by koroviev
Tags: exponential, induction, polynomial
Share this thread:
koroviev
#1
Dec18-11, 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].
Phys.Org News Partner Science news on Phys.org
NASA team lays plans to observe new worlds
IHEP in China has ambitions for Higgs factory
Spinach could lead to alternative energy more powerful than Popeye
micromass
#2
Dec19-11, 01:41 PM
Mentor
micromass's Avatar
P: 18,019
Quote Quote by koroviev View Post
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].
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...
koroviev
#3
Dec19-11, 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}{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].


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 x-5? Calculus & Beyond Homework 5
Which grows faster, (x-4)^3 or... Calculus & Beyond Homework 13
Faster Polynomial Multiplication Precalculus Mathematics Homework 4
Which function grows faster? General Math 3