Is $2^n$ always dominate $n^k$, where $k$ is some fixed natural number
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Is $2^n$ always dominate $n^k$, where $k$ is some fixed natural number.
I have hard time thinking about this? My friend say yes but we are not able to come up with any proper proof and it also feels so counterintuitive. We fixed $k=10$ and tried to put the values of $n$ and $n^10$ seems to be increasing way faster than $2^n$.
Can some one give a general argument for this fact?
real-analysis sequences-and-series inequality real-numbers
asked Sep 3 at 7:21
StammeringMathematician
55616
add a comment |Â
up vote
1
down vote
favorite
Is $2^n$ always dominate $n^k$, where $k$ is some fixed natural number.
I have hard time thinking about this? My friend say yes but we are not able to come up with any proper proof and it also feels so counterintuitive. We fixed $k=10$ and tried to put the values of $n$ and $n^10$ seems to be increasing way faster than $2^n$.
Can some one give a general argument for this fact?
real-analysis sequences-and-series inequality real-numbers
asked Sep 3 at 7:21
StammeringMathematician
55616
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Is $2^n$ always dominate $n^k$, where $k$ is some fixed natural number.
I have hard time thinking about this? My friend say yes but we are not able to come up with any proper proof and it also feels so counterintuitive. We fixed $k=10$ and tried to put the values of $n$ and $n^10$ seems to be increasing way faster than $2^n$.
Can some one give a general argument for this fact?
real-analysis sequences-and-series inequality real-numbers
asked Sep 3 at 7:21
StammeringMathematician
55616
Is $2^n$ always dominate $n^k$, where $k$ is some fixed natural number.
I have hard time thinking about this? My friend say yes but we are not able to come up with any proper proof and it also feels so counterintuitive. We fixed $k=10$ and tried to put the values of $n$ and $n^10$ seems to be increasing way faster than $2^n$.
Can some one give a general argument for this fact?
real-analysis sequences-and-series inequality real-numbers
real-analysis sequences-and-series inequality real-numbers
asked Sep 3 at 7:21
StammeringMathematician
55616
asked Sep 3 at 7:21
StammeringMathematician
55616
asked Sep 3 at 7:21
StammeringMathematician
55616
asked Sep 3 at 7:21
StammeringMathematician
55616
asked Sep 3 at 7:21
StammeringMathematician
55616
55616
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
$2^n >n^k$ iff $ n , log , 2>k, log , n$ iff $frac n log , n >frac k log , 2$ which is true for all $n$ sufficiently large because $frac n log , n to infty$ as $ n to infty$.
answered Sep 3 at 7:25
Kavi Rama Murthy
25.9k31436
You are right. I found values for n=1 up to 10. I now realize that after n=200, $2^n $ will start dominating $n^10$. Thanks. Maths is truly beautiful.
– StammeringMathematician
Sep 3 at 7:32
add a comment |Â
up vote
2
down vote
Another way, without using logarithms, is to examine the binomial expansion as follows:
$$2^n=(1+1)^n=binom n0+binom n1+dots +binom nr+dots binom nn$$
The terms on the right certainly include (for $ngt r+1)$ $$binom nr+1=frac 1(r+1)!cdot n(n-1)dots (n-r)$$
This is a polynomial of degree $r+1$ in $n$ with positive leading coefficient, and it is easy to show that this dominates $n^r$ for $n$ large enough using entirely elementary estimates.
answered Sep 3 at 7:50
Mark Bennet
77.4k774173
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
$2^n >n^k$ iff $ n , log , 2>k, log , n$ iff $frac n log , n >frac k log , 2$ which is true for all $n$ sufficiently large because $frac n log , n to infty$ as $ n to infty$.
answered Sep 3 at 7:25
Kavi Rama Murthy
25.9k31436
You are right. I found values for n=1 up to 10. I now realize that after n=200, $2^n $ will start dominating $n^10$. Thanks. Maths is truly beautiful.
– StammeringMathematician
Sep 3 at 7:32
add a comment |Â
up vote
3
down vote
$2^n >n^k$ iff $ n , log , 2>k, log , n$ iff $frac n log , n >frac k log , 2$ which is true for all $n$ sufficiently large because $frac n log , n to infty$ as $ n to infty$.
answered Sep 3 at 7:25
Kavi Rama Murthy
25.9k31436
You are right. I found values for n=1 up to 10. I now realize that after n=200, $2^n $ will start dominating $n^10$. Thanks. Maths is truly beautiful.
– StammeringMathematician
Sep 3 at 7:32
add a comment |Â
up vote
3
down vote
up vote
3
down vote
$2^n >n^k$ iff $ n , log , 2>k, log , n$ iff $frac n log , n >frac k log , 2$ which is true for all $n$ sufficiently large because $frac n log , n to infty$ as $ n to infty$.
answered Sep 3 at 7:25
Kavi Rama Murthy
25.9k31436
$2^n >n^k$ iff $ n , log , 2>k, log , n$ iff $frac n log , n >frac k log , 2$ which is true for all $n$ sufficiently large because $frac n log , n to infty$ as $ n to infty$.
answered Sep 3 at 7:25
Kavi Rama Murthy
25.9k31436
answered Sep 3 at 7:25
Kavi Rama Murthy
25.9k31436
answered Sep 3 at 7:25
Kavi Rama Murthy
25.9k31436
answered Sep 3 at 7:25
Kavi Rama Murthy
25.9k31436
25.9k31436
You are right. I found values for n=1 up to 10. I now realize that after n=200, $2^n $ will start dominating $n^10$. Thanks. Maths is truly beautiful.
– StammeringMathematician
Sep 3 at 7:32
add a comment |Â
You are right. I found values for n=1 up to 10. I now realize that after n=200, $2^n $ will start dominating $n^10$. Thanks. Maths is truly beautiful.
– StammeringMathematician
Sep 3 at 7:32
You are right. I found values for n=1 up to 10. I now realize that after n=200, $2^n $ will start dominating $n^10$. Thanks. Maths is truly beautiful.
– StammeringMathematician
Sep 3 at 7:32
You are right. I found values for n=1 up to 10. I now realize that after n=200, $2^n $ will start dominating $n^10$. Thanks. Maths is truly beautiful.
– StammeringMathematician
Sep 3 at 7:32
add a comment |Â
up vote
2
down vote
Another way, without using logarithms, is to examine the binomial expansion as follows:
$$2^n=(1+1)^n=binom n0+binom n1+dots +binom nr+dots binom nn$$
The terms on the right certainly include (for $ngt r+1)$ $$binom nr+1=frac 1(r+1)!cdot n(n-1)dots (n-r)$$
This is a polynomial of degree $r+1$ in $n$ with positive leading coefficient, and it is easy to show that this dominates $n^r$ for $n$ large enough using entirely elementary estimates.
answered Sep 3 at 7:50
Mark Bennet
77.4k774173
add a comment |Â
up vote
2
down vote
Another way, without using logarithms, is to examine the binomial expansion as follows:
$$2^n=(1+1)^n=binom n0+binom n1+dots +binom nr+dots binom nn$$
The terms on the right certainly include (for $ngt r+1)$ $$binom nr+1=frac 1(r+1)!cdot n(n-1)dots (n-r)$$
This is a polynomial of degree $r+1$ in $n$ with positive leading coefficient, and it is easy to show that this dominates $n^r$ for $n$ large enough using entirely elementary estimates.
answered Sep 3 at 7:50
Mark Bennet
77.4k774173
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Another way, without using logarithms, is to examine the binomial expansion as follows:
$$2^n=(1+1)^n=binom n0+binom n1+dots +binom nr+dots binom nn$$
The terms on the right certainly include (for $ngt r+1)$ $$binom nr+1=frac 1(r+1)!cdot n(n-1)dots (n-r)$$
This is a polynomial of degree $r+1$ in $n$ with positive leading coefficient, and it is easy to show that this dominates $n^r$ for $n$ large enough using entirely elementary estimates.
answered Sep 3 at 7:50
Mark Bennet
77.4k774173
Another way, without using logarithms, is to examine the binomial expansion as follows:
$$2^n=(1+1)^n=binom n0+binom n1+dots +binom nr+dots binom nn$$
The terms on the right certainly include (for $ngt r+1)$ $$binom nr+1=frac 1(r+1)!cdot n(n-1)dots (n-r)$$
This is a polynomial of degree $r+1$ in $n$ with positive leading coefficient, and it is easy to show that this dominates $n^r$ for $n$ large enough using entirely elementary estimates.
answered Sep 3 at 7:50
Mark Bennet
77.4k774173
answered Sep 3 at 7:50
Mark Bennet
77.4k774173
answered Sep 3 at 7:50
Mark Bennet
77.4k774173
answered Sep 3 at 7:50
Mark Bennet
77.4k774173
77.4k774173
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2903606%2fis-2n-always-dominate-nk-where-k-is-some-fixed-natural-number%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
