Dtjytyk

How to write a macro that is braces sensitive?

Python: next in for loop

A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?

What are the differences between the usage of 'it' and 'they'?

What does it mean to describe someone as a butt steak?

Is it tax fraud for an individual to declare non-taxable revenue as taxable income? (US tax laws)

Risk of getting Chronic Wasting Disease (CWD) in the United States?

What are these boxed doors outside store fronts in New York?

How to format long polynomial?

How do I create uniquely male characters?

How does one intimidate enemies without having the capacity for violence?

What is the offset in a seaplane's hull?

Why doesn't Newton's third law mean a person bounces back to where they started when they hit the ground?

How can I make my BBEG immortal short of making them a Lich or Vampire?

What do the dots in this tr command do: tr .............A-Z A-ZA-Z <<< "JVPQBOV" (with 13 dots)

Arthur Somervell: 1000 Exercises - Meaning of this notation

Why does Kotter return in Welcome Back Kotter?

How do we improve the relationship with a client software team that performs poorly and is becoming less collaborative?

How can bays and straits be determined in a procedurally generated map?

Email Account under attack (really) - anything I can do?

Why was the small council so happy for Tyrion to become the Master of Coin?

Why did the Germans forbid the possession of pet pigeons in Rostov-on-Don in 1941?

How much RAM could one put in a typical 80386 setup?

How is it possible to have an ability score that is less than 3?

How can I prove limit of $n^k$ over $c^n$ is 0?

Prove that exponential functions grow faster than polynomialGeometric Mean limit of $ell_p$ norm of sumsLimit Proof QuestionProve that the following limit exists and find it!Limit property of a function: $lim_{p to 0} frac{w(c p)}{w(p)} in (0,infty)$Solving limit of radicals without L'Hopital $lim_{xto 64} dfrac{sqrt x - 8}{sqrt[3] x - 4} $Limit of infinity times zeroHow to prove $lim_{x to infty} frac{log(1+f(x))}{f(x)} = 1$ without using L'Hopital's rule?What is the limit of the indeterminate form of 1/0?Do we need the axiom of choice to prove L'Hopital's rule?Prove that $lim_{uto infty}{frac{u^m}{e^u}}=0$

-1

0

$begingroup$

How can I prove that
$$
lim_{n to infty}frac{n^k}{c^n}=0 ?
$$
I know it is true by intuition, but I do not know how to prove it.
Here $cgt1, kge1$.

---

BACKGROUND

I am learning time complexity theory and I couldn't find the proof of this in CLRS. It just shows that time complexity of $c^n$ is always greater than $n^k$. Therefore, I cannot understand the proof which uses derivatives like L'Hopital's rule.

limits limits-without-lhopital

share|cite|improve this question

edited Mar 21 at 18:07

Strants

5,80421736

asked Mar 20 at 0:21

Privacy of AnimalPrivacy of Animal

91

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  The way the topics are arranged in certain textbooks, the limit $lim_{n to infty}frac{n^k}{c^n} = 0$ is computed much before the derivative of $c^x$. If Privacy is using such a textbook, then answers using derivatives will not help him. This type of thing may be a reason not to answer such questions until the attempts are shown, telling us what the background of the asker is.
  $endgroup$
  – GEdgar
  Mar 20 at 0:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @GEdgar I edited
  $endgroup$
  – Privacy of Animal
  Mar 20 at 1:34
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is due to exponential functions, with a base $c gt 1$, always eventually grow faster than any polynomial, e.g., $n^k$ in your case. This issue was asked in Prove that exponential functions grow faster than polynomial, with a fairly basic answer provided which doesn't use L'Hopital's rule or anything like that.
  $endgroup$
  – John Omielan
  Mar 20 at 2:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What have you tried?
  $endgroup$
  – clathratus
  Mar 21 at 18:20
  

  
  
  
  

add a comment | 

-1

0

$begingroup$

How can I prove that
$$
lim_{n to infty}frac{n^k}{c^n}=0 ?
$$
I know it is true by intuition, but I do not know how to prove it.
Here $cgt1, kge1$.

---

BACKGROUND

I am learning time complexity theory and I couldn't find the proof of this in CLRS. It just shows that time complexity of $c^n$ is always greater than $n^k$. Therefore, I cannot understand the proof which uses derivatives like L'Hopital's rule.

limits limits-without-lhopital

share|cite|improve this question

edited Mar 21 at 18:07

Strants

5,80421736

asked Mar 20 at 0:21

Privacy of AnimalPrivacy of Animal

91

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  The way the topics are arranged in certain textbooks, the limit $lim_{n to infty}frac{n^k}{c^n} = 0$ is computed much before the derivative of $c^x$. If Privacy is using such a textbook, then answers using derivatives will not help him. This type of thing may be a reason not to answer such questions until the attempts are shown, telling us what the background of the asker is.
  $endgroup$
  – GEdgar
  Mar 20 at 0:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @GEdgar I edited
  $endgroup$
  – Privacy of Animal
  Mar 20 at 1:34
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is due to exponential functions, with a base $c gt 1$, always eventually grow faster than any polynomial, e.g., $n^k$ in your case. This issue was asked in Prove that exponential functions grow faster than polynomial, with a fairly basic answer provided which doesn't use L'Hopital's rule or anything like that.
  $endgroup$
  – John Omielan
  Mar 20 at 2:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What have you tried?
  $endgroup$
  – clathratus
  Mar 21 at 18:20
  

  
  
  
  

add a comment | 

$begingroup$

How can I prove that
$$
lim_{n to infty}frac{n^k}{c^n}=0 ?
$$
I know it is true by intuition, but I do not know how to prove it.
Here $cgt1, kge1$.

---

BACKGROUND

I am learning time complexity theory and I couldn't find the proof of this in CLRS. It just shows that time complexity of $c^n$ is always greater than $n^k$. Therefore, I cannot understand the proof which uses derivatives like L'Hopital's rule.

limits limits-without-lhopital

share|cite|improve this question

edited Mar 21 at 18:07

Strants

5,80421736

asked Mar 20 at 0:21

Privacy of AnimalPrivacy of Animal

91

$endgroup$

share|cite|improve this question

edited Mar 21 at 18:07

Strants

5,80421736

asked Mar 20 at 0:21

Privacy of AnimalPrivacy of Animal

91

share|cite|improve this question

edited Mar 21 at 18:07

Strants

5,80421736

asked Mar 20 at 0:21

Privacy of AnimalPrivacy of Animal

91

edited Mar 21 at 18:07

Strants

5,80421736

edited Mar 21 at 18:07

Strants

5,80421736

asked Mar 20 at 0:21

Privacy of AnimalPrivacy of Animal

91

asked Mar 20 at 0:21

Privacy of AnimalPrivacy of Animal

91

5 Answers
5

active

oldest

votes

1

$begingroup$

You may proceed for example as follows:

• 
  $c > 1 Rightarrow c = 1+p$ with $p > 0$
  

The binomial formula gives for $n geq 1$

• 
  $c^n = (1+p)^n = sum_{i=0}^nbinom{n}{i}p^i Rightarrow c^n > binom{n}{i}p^i$ for each $i = 0,ldots , n$
  

Now, you can estimate as follows for $n > k$:

begin{eqnarray*} 0leq frac{n^k}{c^n}
& = & frac{n^k}{(1+p)^n}\
& < & frac{n^k}{binom{n}{k+1}p^{k+1}}\
& = & frac{n^kcdot (k+1)!}{underbrace{n(n-1)cdots (n-k+1)}_{k ; factors} cdot (n-k) cdot p^{k+1}} \
& < & frac{n^kcdot (k+1)!}{(n-k)^{k+1} cdot p^{k+1}}\
& = & frac{1}{n}cdot frac{(k+1)!}{(1-frac{k}{n})^{k+1} cdot p^{k+1}}\
& stackrel{n to infty}{longrightarrow} & 0 cdot frac{(k+1)!}{p^{k+1}} = 0
end{eqnarray*}

share|cite|improve this answer

answered Mar 20 at 5:37

trancelocationtrancelocation

13.6k1829

$endgroup$

add a comment | 

0

$begingroup$

Hint:

Set $u_n= dfrac{n^k}{c^n}$ and calculate $;dfrac{u_{n+1}}{u_n}$ to find an upper bound of the ratio for $n$ large.

share|cite|improve this answer

answered Mar 20 at 0:32

BernardBernard

124k741116

$endgroup$

add a comment | 

0

$begingroup$

L'Hôpital's rule, applied to this case, says that for $f(n) = n^k$ and $g(n) = c^n$, since $lim_{n to infty} f(n) = infty$ and $lim_{n to infty} g(n) = infty$ and both $f$ and $g$ are differentiable, then
$$lim_{n to infty} frac{f(n)}{g(n)} = lim_{n to infty} frac{f'(n)}{g'(n)} . $$

Thus, after applying L'Hôpital's rule $k$ times you get:
$$lim_{n to infty} frac{k!}{(ln c)^k c^n} = 0 .$$

share|cite|improve this answer

answered Mar 20 at 0:34

ErtxiemErtxiem

661112

$endgroup$

add a comment | 

0

$begingroup$

Without loss of generality, let $k$ be an integer (or take $k$ to be floor[$k+1$]. Apply L'Hopital's rule $k$ times:

$displaystyle lim_{n rightarrow infty } frac{n^k}{c^n} = lim_{nrightarrow infty }frac{k!}{(ln c)^k c^n} = 0.$

share|cite|improve this answer

edited Mar 20 at 0:45

answered Mar 20 at 0:31

mjwmjw

2437

$endgroup$

add a comment | 

0

$begingroup$

Two hints/ideas: try Stolz-Cesaro or consider the series with your expression as general term. If converges, the g.t. -> 0.

share|cite|improve this answer

answered Mar 20 at 5:56

Martín-Blas Pérez PinillaMartín-Blas Pérez Pinilla

35.2k42971

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3154844%2fhow-can-i-prove-limit-of-nk-over-cn-is-0%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

You may proceed for example as follows:

• 
  $c > 1 Rightarrow c = 1+p$ with $p > 0$
  

The binomial formula gives for $n geq 1$

• 
  $c^n = (1+p)^n = sum_{i=0}^nbinom{n}{i}p^i Rightarrow c^n > binom{n}{i}p^i$ for each $i = 0,ldots , n$
  

Now, you can estimate as follows for $n > k$:

begin{eqnarray*} 0leq frac{n^k}{c^n}
& = & frac{n^k}{(1+p)^n}\
& < & frac{n^k}{binom{n}{k+1}p^{k+1}}\
& = & frac{n^kcdot (k+1)!}{underbrace{n(n-1)cdots (n-k+1)}_{k ; factors} cdot (n-k) cdot p^{k+1}} \
& < & frac{n^kcdot (k+1)!}{(n-k)^{k+1} cdot p^{k+1}}\
& = & frac{1}{n}cdot frac{(k+1)!}{(1-frac{k}{n})^{k+1} cdot p^{k+1}}\
& stackrel{n to infty}{longrightarrow} & 0 cdot frac{(k+1)!}{p^{k+1}} = 0
end{eqnarray*}

share|cite|improve this answer

answered Mar 20 at 5:37

trancelocationtrancelocation

13.6k1829

$endgroup$

add a comment | 

1

$begingroup$

You may proceed for example as follows:

• 
  $c > 1 Rightarrow c = 1+p$ with $p > 0$
  

The binomial formula gives for $n geq 1$

• 
  $c^n = (1+p)^n = sum_{i=0}^nbinom{n}{i}p^i Rightarrow c^n > binom{n}{i}p^i$ for each $i = 0,ldots , n$
  

Now, you can estimate as follows for $n > k$:

begin{eqnarray*} 0leq frac{n^k}{c^n}
& = & frac{n^k}{(1+p)^n}\
& < & frac{n^k}{binom{n}{k+1}p^{k+1}}\
& = & frac{n^kcdot (k+1)!}{underbrace{n(n-1)cdots (n-k+1)}_{k ; factors} cdot (n-k) cdot p^{k+1}} \
& < & frac{n^kcdot (k+1)!}{(n-k)^{k+1} cdot p^{k+1}}\
& = & frac{1}{n}cdot frac{(k+1)!}{(1-frac{k}{n})^{k+1} cdot p^{k+1}}\
& stackrel{n to infty}{longrightarrow} & 0 cdot frac{(k+1)!}{p^{k+1}} = 0
end{eqnarray*}

share|cite|improve this answer

answered Mar 20 at 5:37

trancelocationtrancelocation

13.6k1829

$endgroup$

add a comment | 

$begingroup$

You may proceed for example as follows:

• 
  $c > 1 Rightarrow c = 1+p$ with $p > 0$
  

The binomial formula gives for $n geq 1$

• 
  $c^n = (1+p)^n = sum_{i=0}^nbinom{n}{i}p^i Rightarrow c^n > binom{n}{i}p^i$ for each $i = 0,ldots , n$
  

Now, you can estimate as follows for $n > k$:

begin{eqnarray*} 0leq frac{n^k}{c^n}
& = & frac{n^k}{(1+p)^n}\
& < & frac{n^k}{binom{n}{k+1}p^{k+1}}\
& = & frac{n^kcdot (k+1)!}{underbrace{n(n-1)cdots (n-k+1)}_{k ; factors} cdot (n-k) cdot p^{k+1}} \
& < & frac{n^kcdot (k+1)!}{(n-k)^{k+1} cdot p^{k+1}}\
& = & frac{1}{n}cdot frac{(k+1)!}{(1-frac{k}{n})^{k+1} cdot p^{k+1}}\
& stackrel{n to infty}{longrightarrow} & 0 cdot frac{(k+1)!}{p^{k+1}} = 0
end{eqnarray*}

share|cite|improve this answer

answered Mar 20 at 5:37

trancelocationtrancelocation

13.6k1829

$endgroup$

share|cite|improve this answer

answered Mar 20 at 5:37

trancelocationtrancelocation

13.6k1829

answered Mar 20 at 5:37

trancelocationtrancelocation

13.6k1829

answered Mar 20 at 5:37

trancelocationtrancelocation

13.6k1829

0

$begingroup$

Hint:

Set $u_n= dfrac{n^k}{c^n}$ and calculate $;dfrac{u_{n+1}}{u_n}$ to find an upper bound of the ratio for $n$ large.

share|cite|improve this answer

answered Mar 20 at 0:32

BernardBernard

124k741116

$endgroup$

add a comment | 

0

$begingroup$

Hint:

Set $u_n= dfrac{n^k}{c^n}$ and calculate $;dfrac{u_{n+1}}{u_n}$ to find an upper bound of the ratio for $n$ large.

share|cite|improve this answer

answered Mar 20 at 0:32

BernardBernard

124k741116

$endgroup$

add a comment | 

$begingroup$

Hint:

Set $u_n= dfrac{n^k}{c^n}$ and calculate $;dfrac{u_{n+1}}{u_n}$ to find an upper bound of the ratio for $n$ large.

share|cite|improve this answer

answered Mar 20 at 0:32

BernardBernard

124k741116

$endgroup$

share|cite|improve this answer

answered Mar 20 at 0:32

BernardBernard

124k741116

answered Mar 20 at 0:32

BernardBernard

124k741116

answered Mar 20 at 0:32

BernardBernard

124k741116

0

$begingroup$

L'Hôpital's rule, applied to this case, says that for $f(n) = n^k$ and $g(n) = c^n$, since $lim_{n to infty} f(n) = infty$ and $lim_{n to infty} g(n) = infty$ and both $f$ and $g$ are differentiable, then
$$lim_{n to infty} frac{f(n)}{g(n)} = lim_{n to infty} frac{f'(n)}{g'(n)} . $$

Thus, after applying L'Hôpital's rule $k$ times you get:
$$lim_{n to infty} frac{k!}{(ln c)^k c^n} = 0 .$$

share|cite|improve this answer

answered Mar 20 at 0:34

ErtxiemErtxiem

661112

$endgroup$

add a comment | 

0

$begingroup$

L'Hôpital's rule, applied to this case, says that for $f(n) = n^k$ and $g(n) = c^n$, since $lim_{n to infty} f(n) = infty$ and $lim_{n to infty} g(n) = infty$ and both $f$ and $g$ are differentiable, then
$$lim_{n to infty} frac{f(n)}{g(n)} = lim_{n to infty} frac{f'(n)}{g'(n)} . $$

Thus, after applying L'Hôpital's rule $k$ times you get:
$$lim_{n to infty} frac{k!}{(ln c)^k c^n} = 0 .$$

share|cite|improve this answer

answered Mar 20 at 0:34

ErtxiemErtxiem

661112

$endgroup$

add a comment | 

$begingroup$

L'Hôpital's rule, applied to this case, says that for $f(n) = n^k$ and $g(n) = c^n$, since $lim_{n to infty} f(n) = infty$ and $lim_{n to infty} g(n) = infty$ and both $f$ and $g$ are differentiable, then
$$lim_{n to infty} frac{f(n)}{g(n)} = lim_{n to infty} frac{f'(n)}{g'(n)} . $$

Thus, after applying L'Hôpital's rule $k$ times you get:
$$lim_{n to infty} frac{k!}{(ln c)^k c^n} = 0 .$$

share|cite|improve this answer

answered Mar 20 at 0:34

ErtxiemErtxiem

661112

$endgroup$

share|cite|improve this answer

answered Mar 20 at 0:34

ErtxiemErtxiem

661112

answered Mar 20 at 0:34

ErtxiemErtxiem

661112

answered Mar 20 at 0:34

ErtxiemErtxiem

661112

0

$begingroup$

Without loss of generality, let $k$ be an integer (or take $k$ to be floor[$k+1$]. Apply L'Hopital's rule $k$ times:

$displaystyle lim_{n rightarrow infty } frac{n^k}{c^n} = lim_{nrightarrow infty }frac{k!}{(ln c)^k c^n} = 0.$

share|cite|improve this answer

edited Mar 20 at 0:45

answered Mar 20 at 0:31

mjwmjw

2437

$endgroup$

add a comment | 

0

$begingroup$

Without loss of generality, let $k$ be an integer (or take $k$ to be floor[$k+1$]. Apply L'Hopital's rule $k$ times:

$displaystyle lim_{n rightarrow infty } frac{n^k}{c^n} = lim_{nrightarrow infty }frac{k!}{(ln c)^k c^n} = 0.$

share|cite|improve this answer

edited Mar 20 at 0:45

answered Mar 20 at 0:31

mjwmjw

2437

$endgroup$

add a comment | 

$begingroup$

Without loss of generality, let $k$ be an integer (or take $k$ to be floor[$k+1$]. Apply L'Hopital's rule $k$ times:

$displaystyle lim_{n rightarrow infty } frac{n^k}{c^n} = lim_{nrightarrow infty }frac{k!}{(ln c)^k c^n} = 0.$

share|cite|improve this answer

edited Mar 20 at 0:45

answered Mar 20 at 0:31

mjwmjw

2437

$endgroup$

share|cite|improve this answer

edited Mar 20 at 0:45

answered Mar 20 at 0:31

mjwmjw

2437

answered Mar 20 at 0:31

mjwmjw

2437

answered Mar 20 at 0:31

mjwmjw

2437

0

$begingroup$

Two hints/ideas: try Stolz-Cesaro or consider the series with your expression as general term. If converges, the g.t. -> 0.

share|cite|improve this answer

answered Mar 20 at 5:56

Martín-Blas Pérez PinillaMartín-Blas Pérez Pinilla

35.2k42971

$endgroup$

add a comment | 

0

$begingroup$

Two hints/ideas: try Stolz-Cesaro or consider the series with your expression as general term. If converges, the g.t. -> 0.

share|cite|improve this answer

answered Mar 20 at 5:56

Martín-Blas Pérez PinillaMartín-Blas Pérez Pinilla

35.2k42971

$endgroup$

add a comment | 

$begingroup$

Two hints/ideas: try Stolz-Cesaro or consider the series with your expression as general term. If converges, the g.t. -> 0.

share|cite|improve this answer

answered Mar 20 at 5:56

Martín-Blas Pérez PinillaMartín-Blas Pérez Pinilla

35.2k42971

$endgroup$

share|cite|improve this answer

answered Mar 20 at 5:56

Martín-Blas Pérez PinillaMartín-Blas Pérez Pinilla

35.2k42971

answered Mar 20 at 5:56

Martín-Blas Pérez PinillaMartín-Blas Pérez Pinilla

35.2k42971

answered Mar 20 at 5:56

Martín-Blas Pérez PinillaMartín-Blas Pérez Pinilla

35.2k42971