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
Mysterious source of ozone-depleting chemical baffles NASA
Water leads to chemical that gunks up biofuels production
How lizards regenerate their tails: Researchers discover genetic 'recipe'
micromass
#2
Dec19-11, 01:41 PM
Mentor
micromass's Avatar
P: 18,240
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