Growth of Functions proof
How would you prove $n! ∈ Ω(n^{n/2})$ ? This example was given to us in school, but I don't know how to prove it.
What I'am trying to prove:
begin{align}
n! ∈ Ω(n^{n/2})
⇔
∃ c ∈ ℝ^+, ∃ n_0 ∈ ℕ^+, ∀ n ≥ n_0 : cn^{n/2} ≤ n!
end{align}
What I tried was induction:
1)
begin{align}
n=1, c=1: √1 ≤ 1
end{align}
2)
begin{align}
(cn^{n/2} ≤ n!) ⇒ c(n+1)^{(n+1)/2} ≤ (n+1)!\
c(n+1)^{((n+1)/2)-1}(n+1)≤ (n+1)n!\
c(n+1)^{((n+1)/2)-1} ≤ n!
end{align}
This is the part where I get stuck and don't know how to end the proof.
Thank you for response.
proof-writing algorithms proof-explanation computer-science
asked Nov 24 at 18:28
Talos
82
add a comment |
How would you prove $n! ∈ Ω(n^{n/2})$ ? This example was given to us in school, but I don't know how to prove it.
What I'am trying to prove:
begin{align}
n! ∈ Ω(n^{n/2})
⇔
∃ c ∈ ℝ^+, ∃ n_0 ∈ ℕ^+, ∀ n ≥ n_0 : cn^{n/2} ≤ n!
end{align}
What I tried was induction:
1)
begin{align}
n=1, c=1: √1 ≤ 1
end{align}
2)
begin{align}
(cn^{n/2} ≤ n!) ⇒ c(n+1)^{(n+1)/2} ≤ (n+1)!\
c(n+1)^{((n+1)/2)-1}(n+1)≤ (n+1)n!\
c(n+1)^{((n+1)/2)-1} ≤ n!
end{align}
This is the part where I get stuck and don't know how to end the proof.
Thank you for response.
proof-writing algorithms proof-explanation computer-science
asked Nov 24 at 18:28
Talos
82
Are you familiar with Stirling's approximation?
– mrtaurho
Nov 24 at 18:34
I know that it is used to get factorial approximation. Does it has to be used in this proof ?
– Talos
Nov 24 at 18:37
add a comment |
How would you prove $n! ∈ Ω(n^{n/2})$ ? This example was given to us in school, but I don't know how to prove it.
What I'am trying to prove:
begin{align}
n! ∈ Ω(n^{n/2})
⇔
∃ c ∈ ℝ^+, ∃ n_0 ∈ ℕ^+, ∀ n ≥ n_0 : cn^{n/2} ≤ n!
end{align}
What I tried was induction:
1)
begin{align}
n=1, c=1: √1 ≤ 1
end{align}
2)
begin{align}
(cn^{n/2} ≤ n!) ⇒ c(n+1)^{(n+1)/2} ≤ (n+1)!\
c(n+1)^{((n+1)/2)-1}(n+1)≤ (n+1)n!\
c(n+1)^{((n+1)/2)-1} ≤ n!
end{align}
This is the part where I get stuck and don't know how to end the proof.
Thank you for response.
proof-writing algorithms proof-explanation computer-science
asked Nov 24 at 18:28
Talos
82
How would you prove $n! ∈ Ω(n^{n/2})$ ? This example was given to us in school, but I don't know how to prove it.
What I'am trying to prove:
begin{align}
n! ∈ Ω(n^{n/2})
⇔
∃ c ∈ ℝ^+, ∃ n_0 ∈ ℕ^+, ∀ n ≥ n_0 : cn^{n/2} ≤ n!
end{align}
What I tried was induction:
1)
begin{align}
n=1, c=1: √1 ≤ 1
end{align}
2)
begin{align}
(cn^{n/2} ≤ n!) ⇒ c(n+1)^{(n+1)/2} ≤ (n+1)!\
c(n+1)^{((n+1)/2)-1}(n+1)≤ (n+1)n!\
c(n+1)^{((n+1)/2)-1} ≤ n!
end{align}
This is the part where I get stuck and don't know how to end the proof.
Thank you for response.
proof-writing algorithms proof-explanation computer-science
proof-writing algorithms proof-explanation computer-science
asked Nov 24 at 18:28
Talos
82
asked Nov 24 at 18:28
Talos
82
asked Nov 24 at 18:28
Talos
82
asked Nov 24 at 18:28
Talos
82
asked Nov 24 at 18:28
Talos
82
82
Are you familiar with Stirling's approximation?
– mrtaurho
Nov 24 at 18:34
I know that it is used to get factorial approximation. Does it has to be used in this proof ?
– Talos
Nov 24 at 18:37
add a comment |
Are you familiar with Stirling's approximation?
– mrtaurho
Nov 24 at 18:34
I know that it is used to get factorial approximation. Does it has to be used in this proof ?
– Talos
Nov 24 at 18:37
Are you familiar with Stirling's approximation?
– mrtaurho
Nov 24 at 18:34
Are you familiar with Stirling's approximation?
– mrtaurho
Nov 24 at 18:34
I know that it is used to get factorial approximation. Does it has to be used in this proof ?
– Talos
Nov 24 at 18:37
I know that it is used to get factorial approximation. Does it has to be used in this proof ?
– Talos
Nov 24 at 18:37
add a comment |
1 Answer
1
active
oldest
votes
I am not that familiar with these kinds of proofs but I would suggest, as pointed out within the comments, to use Stirling's approximation for the factorial here. This can be seen as an extended comment since my argumentation is not completely sufficient.
We want to show that $cn^{n/2}le n!$ for $n$ greater than some $n_0$. Lets consider Stirling's approximation and do a little bit of reshaping on it.
$$n!simsqrt{2pi n}left(frac neright)^n=frac{sqrt{2pi}}{e^n}n^{n+frac12}$$
where the term infront of the power of $n$ is just a dercreasing term as $n$ goes up to infinity. Reconsider our given inequality and plug in the final form of Stirling's approximation
$$begin{align}
cn^{n/2}&le n!\
&=frac{sqrt{2pi}}{e^n}n^{n+frac12}\
cn^{n/2}&leunderbrace{frac{sqrt{2pi}}{e^n}}_{approx k}n^{n+frac12}
end{align}$$
The marked term $k$ can be seen as a constant in some way. I am not sure how to argue about this in a proper way to be honest. But nevertheless this leaves us with
$$begin{align}
cn^{n/2}&le k n^{n+frac12}
end{align}$$
from which one we can conclude that the RHS is bigger than the LHS side depending on a constant $l=frac ck$.
answered Nov 24 at 18:53
mrtaurho
3,1131930
Thank you. I think this is completely sufficent proof. Many similar proofs end like this. AD: These kind of proofs are crucial for computer science. They answer the questions like "Is this algorithm fast or is it as fast as ... ?". More reading here: cs.sfu.ca/~ggbaker/zju/math/growth.html
– Talos
Nov 24 at 20:07
In this case I am glad that I could help you :)
– mrtaurho
Nov 24 at 20:15
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
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3011901%2fgrowth-of-functions-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I am not that familiar with these kinds of proofs but I would suggest, as pointed out within the comments, to use Stirling's approximation for the factorial here. This can be seen as an extended comment since my argumentation is not completely sufficient.
We want to show that $cn^{n/2}le n!$ for $n$ greater than some $n_0$. Lets consider Stirling's approximation and do a little bit of reshaping on it.
$$n!simsqrt{2pi n}left(frac neright)^n=frac{sqrt{2pi}}{e^n}n^{n+frac12}$$
where the term infront of the power of $n$ is just a dercreasing term as $n$ goes up to infinity. Reconsider our given inequality and plug in the final form of Stirling's approximation
$$begin{align}
cn^{n/2}&le n!\
&=frac{sqrt{2pi}}{e^n}n^{n+frac12}\
cn^{n/2}&leunderbrace{frac{sqrt{2pi}}{e^n}}_{approx k}n^{n+frac12}
end{align}$$
The marked term $k$ can be seen as a constant in some way. I am not sure how to argue about this in a proper way to be honest. But nevertheless this leaves us with
$$begin{align}
cn^{n/2}&le k n^{n+frac12}
end{align}$$
from which one we can conclude that the RHS is bigger than the LHS side depending on a constant $l=frac ck$.
answered Nov 24 at 18:53
mrtaurho
3,1131930
Thank you. I think this is completely sufficent proof. Many similar proofs end like this. AD: These kind of proofs are crucial for computer science. They answer the questions like "Is this algorithm fast or is it as fast as ... ?". More reading here: cs.sfu.ca/~ggbaker/zju/math/growth.html
– Talos
Nov 24 at 20:07
In this case I am glad that I could help you :)
– mrtaurho
Nov 24 at 20:15
add a comment |
I am not that familiar with these kinds of proofs but I would suggest, as pointed out within the comments, to use Stirling's approximation for the factorial here. This can be seen as an extended comment since my argumentation is not completely sufficient.
We want to show that $cn^{n/2}le n!$ for $n$ greater than some $n_0$. Lets consider Stirling's approximation and do a little bit of reshaping on it.
$$n!simsqrt{2pi n}left(frac neright)^n=frac{sqrt{2pi}}{e^n}n^{n+frac12}$$
where the term infront of the power of $n$ is just a dercreasing term as $n$ goes up to infinity. Reconsider our given inequality and plug in the final form of Stirling's approximation
$$begin{align}
cn^{n/2}&le n!\
&=frac{sqrt{2pi}}{e^n}n^{n+frac12}\
cn^{n/2}&leunderbrace{frac{sqrt{2pi}}{e^n}}_{approx k}n^{n+frac12}
end{align}$$
The marked term $k$ can be seen as a constant in some way. I am not sure how to argue about this in a proper way to be honest. But nevertheless this leaves us with
$$begin{align}
cn^{n/2}&le k n^{n+frac12}
end{align}$$
from which one we can conclude that the RHS is bigger than the LHS side depending on a constant $l=frac ck$.
answered Nov 24 at 18:53
mrtaurho
3,1131930
Thank you. I think this is completely sufficent proof. Many similar proofs end like this. AD: These kind of proofs are crucial for computer science. They answer the questions like "Is this algorithm fast or is it as fast as ... ?". More reading here: cs.sfu.ca/~ggbaker/zju/math/growth.html
– Talos
Nov 24 at 20:07
In this case I am glad that I could help you :)
– mrtaurho
Nov 24 at 20:15
add a comment |
I am not that familiar with these kinds of proofs but I would suggest, as pointed out within the comments, to use Stirling's approximation for the factorial here. This can be seen as an extended comment since my argumentation is not completely sufficient.
We want to show that $cn^{n/2}le n!$ for $n$ greater than some $n_0$. Lets consider Stirling's approximation and do a little bit of reshaping on it.
$$n!simsqrt{2pi n}left(frac neright)^n=frac{sqrt{2pi}}{e^n}n^{n+frac12}$$
where the term infront of the power of $n$ is just a dercreasing term as $n$ goes up to infinity. Reconsider our given inequality and plug in the final form of Stirling's approximation
$$begin{align}
cn^{n/2}&le n!\
&=frac{sqrt{2pi}}{e^n}n^{n+frac12}\
cn^{n/2}&leunderbrace{frac{sqrt{2pi}}{e^n}}_{approx k}n^{n+frac12}
end{align}$$
The marked term $k$ can be seen as a constant in some way. I am not sure how to argue about this in a proper way to be honest. But nevertheless this leaves us with
$$begin{align}
cn^{n/2}&le k n^{n+frac12}
end{align}$$
from which one we can conclude that the RHS is bigger than the LHS side depending on a constant $l=frac ck$.
answered Nov 24 at 18:53
mrtaurho
3,1131930
I am not that familiar with these kinds of proofs but I would suggest, as pointed out within the comments, to use Stirling's approximation for the factorial here. This can be seen as an extended comment since my argumentation is not completely sufficient.
We want to show that $cn^{n/2}le n!$ for $n$ greater than some $n_0$. Lets consider Stirling's approximation and do a little bit of reshaping on it.
$$n!simsqrt{2pi n}left(frac neright)^n=frac{sqrt{2pi}}{e^n}n^{n+frac12}$$
where the term infront of the power of $n$ is just a dercreasing term as $n$ goes up to infinity. Reconsider our given inequality and plug in the final form of Stirling's approximation
$$begin{align}
cn^{n/2}&le n!\
&=frac{sqrt{2pi}}{e^n}n^{n+frac12}\
cn^{n/2}&leunderbrace{frac{sqrt{2pi}}{e^n}}_{approx k}n^{n+frac12}
end{align}$$
The marked term $k$ can be seen as a constant in some way. I am not sure how to argue about this in a proper way to be honest. But nevertheless this leaves us with
$$begin{align}
cn^{n/2}&le k n^{n+frac12}
end{align}$$
from which one we can conclude that the RHS is bigger than the LHS side depending on a constant $l=frac ck$.
answered Nov 24 at 18:53
mrtaurho
3,1131930
answered Nov 24 at 18:53
mrtaurho
3,1131930
answered Nov 24 at 18:53
mrtaurho
3,1131930
answered Nov 24 at 18:53
mrtaurho
3,1131930
3,1131930
Thank you. I think this is completely sufficent proof. Many similar proofs end like this. AD: These kind of proofs are crucial for computer science. They answer the questions like "Is this algorithm fast or is it as fast as ... ?". More reading here: cs.sfu.ca/~ggbaker/zju/math/growth.html
– Talos
Nov 24 at 20:07
In this case I am glad that I could help you :)
– mrtaurho
Nov 24 at 20:15
add a comment |
Thank you. I think this is completely sufficent proof. Many similar proofs end like this. AD: These kind of proofs are crucial for computer science. They answer the questions like "Is this algorithm fast or is it as fast as ... ?". More reading here: cs.sfu.ca/~ggbaker/zju/math/growth.html
– Talos
Nov 24 at 20:07
In this case I am glad that I could help you :)
– mrtaurho
Nov 24 at 20:15
Thank you. I think this is completely sufficent proof. Many similar proofs end like this. AD: These kind of proofs are crucial for computer science. They answer the questions like "Is this algorithm fast or is it as fast as ... ?". More reading here: cs.sfu.ca/~ggbaker/zju/math/growth.html
– Talos
Nov 24 at 20:07
Thank you. I think this is completely sufficent proof. Many similar proofs end like this. AD: These kind of proofs are crucial for computer science. They answer the questions like "Is this algorithm fast or is it as fast as ... ?". More reading here: cs.sfu.ca/~ggbaker/zju/math/growth.html
– Talos
Nov 24 at 20:07
In this case I am glad that I could help you :)
– mrtaurho
Nov 24 at 20:15
In this case I am glad that I could help you :)
– mrtaurho
Nov 24 at 20:15
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3011901%2fgrowth-of-functions-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Are you familiar with Stirling's approximation?
– mrtaurho
Nov 24 at 18:34
I know that it is used to get factorial approximation. Does it has to be used in this proof ?
– Talos
Nov 24 at 18:37