Mixing
Prove by induction that $n^3 leq 3^n$ for all integers $geq 3$
$begingroup$
I have done easier induction proofs but I got stuck on this one. I start with checking the base case:
$$3^3 leq 3^3$$
$$27 leq 27$$
So the base case holds. Next I assume it works for $p+1$ and want to prove it for $p + 1$ and this is where I get stuck. I start by plugging in $p+1$ in the left side of the inequality:
$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1$$
but then I don't know what to do? I gave up and I checked my book and the next step is this:
$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
But where did p^3 +p^3 +p^2 +1 come from? I don't understand it. I want to reach the end where I can see that (p+1)^3 is indeed less than 3^(p+1) but I get stuck on "p^3 +p^3 +p^2 +1" because I have no idea where they got that from.
If someone could explain you would really make my day!
induction
asked Apr 16 '17 at 18:31
user5846939user5846939
663
$endgroup$
add a comment |
$begingroup$
I have done easier induction proofs but I got stuck on this one. I start with checking the base case:
$$3^3 leq 3^3$$
$$27 leq 27$$
So the base case holds. Next I assume it works for $p+1$ and want to prove it for $p + 1$ and this is where I get stuck. I start by plugging in $p+1$ in the left side of the inequality:
$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1$$
but then I don't know what to do? I gave up and I checked my book and the next step is this:
$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
But where did p^3 +p^3 +p^2 +1 come from? I don't understand it. I want to reach the end where I can see that (p+1)^3 is indeed less than 3^(p+1) but I get stuck on "p^3 +p^3 +p^2 +1" because I have no idea where they got that from.
If someone could explain you would really make my day!
induction
asked Apr 16 '17 at 18:31
user5846939user5846939
663
$endgroup$
1
$begingroup$
Is $p3+p3+p2+1$ supposed to say $p^3+p^3+p^2+1$? If so, then this is because $3p^2 leq pcdot p^2 =p^3$ (since the base case is $p=3$, so certainly $3 leq p$). Similaly $3p leq pcdot p=p^2$.
$endgroup$
– kccu
Apr 16 '17 at 18:38
$begingroup$
Yes I was about to help edit, and I also wondered that part.
$endgroup$
– mathreadler
Apr 16 '17 at 18:39
$begingroup$
By the way welcome to the site. Please consider learning MathJax as it is used for typesetting math. It gets easier to read and increases chances of good responses to questions.
$endgroup$
– mathreadler
Apr 16 '17 at 18:41
add a comment |
$begingroup$
I have done easier induction proofs but I got stuck on this one. I start with checking the base case:
$$3^3 leq 3^3$$
$$27 leq 27$$
So the base case holds. Next I assume it works for $p+1$ and want to prove it for $p + 1$ and this is where I get stuck. I start by plugging in $p+1$ in the left side of the inequality:
$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1$$
but then I don't know what to do? I gave up and I checked my book and the next step is this:
$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
But where did p^3 +p^3 +p^2 +1 come from? I don't understand it. I want to reach the end where I can see that (p+1)^3 is indeed less than 3^(p+1) but I get stuck on "p^3 +p^3 +p^2 +1" because I have no idea where they got that from.
If someone could explain you would really make my day!
induction
asked Apr 16 '17 at 18:31
user5846939user5846939
663
$endgroup$
I have done easier induction proofs but I got stuck on this one. I start with checking the base case:
$$3^3 leq 3^3$$
$$27 leq 27$$
So the base case holds. Next I assume it works for $p+1$ and want to prove it for $p + 1$ and this is where I get stuck. I start by plugging in $p+1$ in the left side of the inequality:
$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1$$
but then I don't know what to do? I gave up and I checked my book and the next step is this:
$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
But where did p^3 +p^3 +p^2 +1 come from? I don't understand it. I want to reach the end where I can see that (p+1)^3 is indeed less than 3^(p+1) but I get stuck on "p^3 +p^3 +p^2 +1" because I have no idea where they got that from.
If someone could explain you would really make my day!
induction
induction
asked Apr 16 '17 at 18:31
user5846939user5846939
663
asked Apr 16 '17 at 18:31
user5846939user5846939
663
edited Apr 16 '17 at 18:43
user5846939
asked Apr 16 '17 at 18:31
user5846939user5846939
663
asked Apr 16 '17 at 18:31
user5846939user5846939
663
asked Apr 16 '17 at 18:31
user5846939user5846939
663
663
1
$begingroup$
Is $p3+p3+p2+1$ supposed to say $p^3+p^3+p^2+1$? If so, then this is because $3p^2 leq pcdot p^2 =p^3$ (since the base case is $p=3$, so certainly $3 leq p$). Similaly $3p leq pcdot p=p^2$.
$endgroup$
– kccu
Apr 16 '17 at 18:38
$begingroup$
Yes I was about to help edit, and I also wondered that part.
$endgroup$
– mathreadler
Apr 16 '17 at 18:39
$begingroup$
By the way welcome to the site. Please consider learning MathJax as it is used for typesetting math. It gets easier to read and increases chances of good responses to questions.
$endgroup$
– mathreadler
Apr 16 '17 at 18:41
add a comment |
1
$begingroup$
Is $p3+p3+p2+1$ supposed to say $p^3+p^3+p^2+1$? If so, then this is because $3p^2 leq pcdot p^2 =p^3$ (since the base case is $p=3$, so certainly $3 leq p$). Similaly $3p leq pcdot p=p^2$.
$endgroup$
– kccu
Apr 16 '17 at 18:38
$begingroup$
Yes I was about to help edit, and I also wondered that part.
$endgroup$
– mathreadler
Apr 16 '17 at 18:39
$begingroup$
By the way welcome to the site. Please consider learning MathJax as it is used for typesetting math. It gets easier to read and increases chances of good responses to questions.
$endgroup$
– mathreadler
Apr 16 '17 at 18:41
1
1
$begingroup$
Is $p3+p3+p2+1$ supposed to say $p^3+p^3+p^2+1$? If so, then this is because $3p^2 leq pcdot p^2 =p^3$ (since the base case is $p=3$, so certainly $3 leq p$). Similaly $3p leq pcdot p=p^2$.
$endgroup$
– kccu
Apr 16 '17 at 18:38
$begingroup$
Is $p3+p3+p2+1$ supposed to say $p^3+p^3+p^2+1$? If so, then this is because $3p^2 leq pcdot p^2 =p^3$ (since the base case is $p=3$, so certainly $3 leq p$). Similaly $3p leq pcdot p=p^2$.
$endgroup$
– kccu
Apr 16 '17 at 18:38
$begingroup$
Yes I was about to help edit, and I also wondered that part.
$endgroup$
– mathreadler
Apr 16 '17 at 18:39
$begingroup$
Yes I was about to help edit, and I also wondered that part.
$endgroup$
– mathreadler
Apr 16 '17 at 18:39
$begingroup$
By the way welcome to the site. Please consider learning MathJax as it is used for typesetting math. It gets easier to read and increases chances of good responses to questions.
$endgroup$
– mathreadler
Apr 16 '17 at 18:41
$begingroup$
By the way welcome to the site. Please consider learning MathJax as it is used for typesetting math. It gets easier to read and increases chances of good responses to questions.
$endgroup$
– mathreadler
Apr 16 '17 at 18:41
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
you must show that from $$n^3le 3^n$$ follows $$(n+1)^3le 3^{n+1}$$
multiplying the inequality $$n^3le 3^n$$ by $3$ we get
$$3n^3le 3^{n+1}$$ but we have
$$(n+1)^3=n^3+3n^2+3n+1le 3n^3$$ if $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
answered Apr 16 '17 at 18:40
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
77.2k42866
$endgroup$
$begingroup$
How did you say that $$n^3+3n^2+3n+1le 3n^3$$
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:42
$begingroup$
this is true since we have $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:44
$begingroup$
That rearrangement is trivial, but how would you prove that that cubic equation is always positive?
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:46
$begingroup$
let $$f(x)=2x^3-3x^2-3x-1$$ and discuss this function for $$xgeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:48
$begingroup$
Honestly, I don't even understand now, why are you just manipulating equations, how will did you see so fast(while answering) that this inequality must hold true?
$endgroup$
– Jaideep Khare
Apr 17 '17 at 12:02
add a comment |
$begingroup$
Since $frac{n+1}{n}$ is stricly decreasing for $nge 3$, we have $$(frac{n+1}{n})^3le (frac{4}{3})^3<3$$ for $nge 3$.
Hence we have , if we assume $n^3le3^n$ : $$(n+1)^3<3n^3le3cdot 3^n=3^{n+1}$$ As an additional result, we have $n^3<3^n$ for $nge 4$
answered Apr 16 '17 at 18:42
PeterPeter
48.5k1139135
$endgroup$
add a comment |
$begingroup$
This answer only explains the inequality
$$p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
you said your book gives. I won't speculate on how they proceed from there to the full result and/or how you could have circumvented using this inequality altogether. (See some of the other answers for more on that last point.)
What they do is for each term on the left find a term (on the right) that is at least as big. So we really have 4 inequalities:
$$p^3 leq p^3$$
$$3p^2 leq p^3$$
$$3p leq p^2$$
$$1 leq 1$$
I guess the outermost two are obvious. To see why the other two hold, remember that $p^3 = p cdot p^2$ and $p^2 = p cdot p$.
UPDATE: the above explains why the inequality is true, but it dawned on me that perhaps your question is how they came up with the terms on the right hand site in the first place.
The answer is: they want, on the right hand side terms that 'look like' $p^3$ because $p^3$ is something they can handle. The reason for that is that the Induction Hypothesis tells us that $p^3 leq 3^p$, so applying the IH takes us finally away from the world of $p^textrm{something}$ to the desired world of $3^{textrm{some expression in } p}$.
But in order to do that, we need our $p^textrm{something}$ to be in the specific form $p^3$.
Hence replacing two out of four of the annoying terms on the left hand side by the more beloved (because appearing in the IH) $p^3$ is already pretty good. And I speculate that their next move will be to note that $p^2 + 1 leq p^3$ (for $p geq 3$)so that we can write:
[all the previous stuff] $leq p^3 + p^3 + p^3$.
Now we are in a position to apply the Induction Hypothesis to obtain
[everything we talked about so far] $leq 3^p + 3^p + 3^p$,
from which it is only a small step to the final answer.
answered Apr 16 '17 at 18:45
VincentVincent
3,35611229
$endgroup$
$begingroup$
What? But the right side of the inequality only says 3^n. So why isn't the right side only 3^(p+1)? I dont understand what you mean with they just find a term. Where do they get p^3 + p^3 + p^2 + 1 from?
$endgroup$
– user5846939
Apr 16 '17 at 19:11
$begingroup$
@user5846939 I am solely talking about the in equality at the top of this answer: the one you said you got stuck on when reading your book. When I say left or right hand side I mean the left and right hand side of that inequality, not of the more interesting inequality n^3 leq 3^n$. So both the left hand side and the right hand side have 4 terms and the truth of the inequality follows from the fact that the first on the left is smaller/equal than the first on the right, the second on the left is smaller/equal than the second on the right etc.
$endgroup$
– Vincent
Apr 17 '17 at 20:36
$begingroup$
@user5846939 I updated my answer to include some stuff on what I believe was going on in the minds of the people who wrote your book. I hope this helps
$endgroup$
– Vincent
Apr 17 '17 at 21:59
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%2f2237199%2fprove-by-induction-that-n3-leq-3n-for-all-integers-geq-3%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
you must show that from $$n^3le 3^n$$ follows $$(n+1)^3le 3^{n+1}$$
multiplying the inequality $$n^3le 3^n$$ by $3$ we get
$$3n^3le 3^{n+1}$$ but we have
$$(n+1)^3=n^3+3n^2+3n+1le 3n^3$$ if $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
answered Apr 16 '17 at 18:40
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
77.2k42866
$endgroup$
$begingroup$
How did you say that $$n^3+3n^2+3n+1le 3n^3$$
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:42
$begingroup$
this is true since we have $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:44
$begingroup$
That rearrangement is trivial, but how would you prove that that cubic equation is always positive?
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:46
$begingroup$
let $$f(x)=2x^3-3x^2-3x-1$$ and discuss this function for $$xgeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:48
$begingroup$
Honestly, I don't even understand now, why are you just manipulating equations, how will did you see so fast(while answering) that this inequality must hold true?
$endgroup$
– Jaideep Khare
Apr 17 '17 at 12:02
add a comment |
$begingroup$
you must show that from $$n^3le 3^n$$ follows $$(n+1)^3le 3^{n+1}$$
multiplying the inequality $$n^3le 3^n$$ by $3$ we get
$$3n^3le 3^{n+1}$$ but we have
$$(n+1)^3=n^3+3n^2+3n+1le 3n^3$$ if $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
answered Apr 16 '17 at 18:40
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
77.2k42866
$endgroup$
$begingroup$
How did you say that $$n^3+3n^2+3n+1le 3n^3$$
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:42
$begingroup$
this is true since we have $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:44
$begingroup$
That rearrangement is trivial, but how would you prove that that cubic equation is always positive?
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:46
$begingroup$
let $$f(x)=2x^3-3x^2-3x-1$$ and discuss this function for $$xgeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:48
$begingroup$
Honestly, I don't even understand now, why are you just manipulating equations, how will did you see so fast(while answering) that this inequality must hold true?
$endgroup$
– Jaideep Khare
Apr 17 '17 at 12:02
add a comment |
$begingroup$
you must show that from $$n^3le 3^n$$ follows $$(n+1)^3le 3^{n+1}$$
multiplying the inequality $$n^3le 3^n$$ by $3$ we get
$$3n^3le 3^{n+1}$$ but we have
$$(n+1)^3=n^3+3n^2+3n+1le 3n^3$$ if $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
answered Apr 16 '17 at 18:40
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
77.2k42866
$endgroup$
you must show that from $$n^3le 3^n$$ follows $$(n+1)^3le 3^{n+1}$$
multiplying the inequality $$n^3le 3^n$$ by $3$ we get
$$3n^3le 3^{n+1}$$ but we have
$$(n+1)^3=n^3+3n^2+3n+1le 3n^3$$ if $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
answered Apr 16 '17 at 18:40
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
77.2k42866
answered Apr 16 '17 at 18:40
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
77.2k42866
answered Apr 16 '17 at 18:40
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
77.2k42866
answered Apr 16 '17 at 18:40
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
77.2k42866
77.2k42866
$begingroup$
How did you say that $$n^3+3n^2+3n+1le 3n^3$$
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:42
$begingroup$
this is true since we have $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:44
$begingroup$
That rearrangement is trivial, but how would you prove that that cubic equation is always positive?
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:46
$begingroup$
let $$f(x)=2x^3-3x^2-3x-1$$ and discuss this function for $$xgeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:48
$begingroup$
Honestly, I don't even understand now, why are you just manipulating equations, how will did you see so fast(while answering) that this inequality must hold true?
$endgroup$
– Jaideep Khare
Apr 17 '17 at 12:02
add a comment |
$begingroup$
How did you say that $$n^3+3n^2+3n+1le 3n^3$$
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:42
$begingroup$
this is true since we have $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:44
$begingroup$
That rearrangement is trivial, but how would you prove that that cubic equation is always positive?
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:46
$begingroup$
let $$f(x)=2x^3-3x^2-3x-1$$ and discuss this function for $$xgeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:48
$begingroup$
Honestly, I don't even understand now, why are you just manipulating equations, how will did you see so fast(while answering) that this inequality must hold true?
$endgroup$
– Jaideep Khare
Apr 17 '17 at 12:02
$begingroup$
How did you say that $$n^3+3n^2+3n+1le 3n^3$$
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:42
$begingroup$
How did you say that $$n^3+3n^2+3n+1le 3n^3$$
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:42
$begingroup$
this is true since we have $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:44
$begingroup$
this is true since we have $$2n^3-3n^2-3n-1geq 0$$ for $$ngeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:44
$begingroup$
That rearrangement is trivial, but how would you prove that that cubic equation is always positive?
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:46
$begingroup$
That rearrangement is trivial, but how would you prove that that cubic equation is always positive?
$endgroup$
– Jaideep Khare
Apr 16 '17 at 18:46
$begingroup$
let $$f(x)=2x^3-3x^2-3x-1$$ and discuss this function for $$xgeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:48
$begingroup$
let $$f(x)=2x^3-3x^2-3x-1$$ and discuss this function for $$xgeq 3$$
$endgroup$
– Dr. Sonnhard Graubner
Apr 16 '17 at 18:48
$begingroup$
Honestly, I don't even understand now, why are you just manipulating equations, how will did you see so fast(while answering) that this inequality must hold true?
$endgroup$
– Jaideep Khare
Apr 17 '17 at 12:02
$begingroup$
Honestly, I don't even understand now, why are you just manipulating equations, how will did you see so fast(while answering) that this inequality must hold true?
$endgroup$
– Jaideep Khare
Apr 17 '17 at 12:02
add a comment |
$begingroup$
Since $frac{n+1}{n}$ is stricly decreasing for $nge 3$, we have $$(frac{n+1}{n})^3le (frac{4}{3})^3<3$$ for $nge 3$.
Hence we have , if we assume $n^3le3^n$ : $$(n+1)^3<3n^3le3cdot 3^n=3^{n+1}$$ As an additional result, we have $n^3<3^n$ for $nge 4$
answered Apr 16 '17 at 18:42
PeterPeter
48.5k1139135
$endgroup$
add a comment |
$begingroup$
Since $frac{n+1}{n}$ is stricly decreasing for $nge 3$, we have $$(frac{n+1}{n})^3le (frac{4}{3})^3<3$$ for $nge 3$.
Hence we have , if we assume $n^3le3^n$ : $$(n+1)^3<3n^3le3cdot 3^n=3^{n+1}$$ As an additional result, we have $n^3<3^n$ for $nge 4$
answered Apr 16 '17 at 18:42
PeterPeter
48.5k1139135
$endgroup$
add a comment |
$begingroup$
Since $frac{n+1}{n}$ is stricly decreasing for $nge 3$, we have $$(frac{n+1}{n})^3le (frac{4}{3})^3<3$$ for $nge 3$.
Hence we have , if we assume $n^3le3^n$ : $$(n+1)^3<3n^3le3cdot 3^n=3^{n+1}$$ As an additional result, we have $n^3<3^n$ for $nge 4$
answered Apr 16 '17 at 18:42
PeterPeter
48.5k1139135
$endgroup$
Since $frac{n+1}{n}$ is stricly decreasing for $nge 3$, we have $$(frac{n+1}{n})^3le (frac{4}{3})^3<3$$ for $nge 3$.
Hence we have , if we assume $n^3le3^n$ : $$(n+1)^3<3n^3le3cdot 3^n=3^{n+1}$$ As an additional result, we have $n^3<3^n$ for $nge 4$
answered Apr 16 '17 at 18:42
PeterPeter
48.5k1139135
answered Apr 16 '17 at 18:42
PeterPeter
48.5k1139135
answered Apr 16 '17 at 18:42
PeterPeter
48.5k1139135
answered Apr 16 '17 at 18:42
PeterPeter
48.5k1139135
48.5k1139135
add a comment |
add a comment |
$begingroup$
This answer only explains the inequality
$$p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
you said your book gives. I won't speculate on how they proceed from there to the full result and/or how you could have circumvented using this inequality altogether. (See some of the other answers for more on that last point.)
What they do is for each term on the left find a term (on the right) that is at least as big. So we really have 4 inequalities:
$$p^3 leq p^3$$
$$3p^2 leq p^3$$
$$3p leq p^2$$
$$1 leq 1$$
I guess the outermost two are obvious. To see why the other two hold, remember that $p^3 = p cdot p^2$ and $p^2 = p cdot p$.
UPDATE: the above explains why the inequality is true, but it dawned on me that perhaps your question is how they came up with the terms on the right hand site in the first place.
The answer is: they want, on the right hand side terms that 'look like' $p^3$ because $p^3$ is something they can handle. The reason for that is that the Induction Hypothesis tells us that $p^3 leq 3^p$, so applying the IH takes us finally away from the world of $p^textrm{something}$ to the desired world of $3^{textrm{some expression in } p}$.
But in order to do that, we need our $p^textrm{something}$ to be in the specific form $p^3$.
Hence replacing two out of four of the annoying terms on the left hand side by the more beloved (because appearing in the IH) $p^3$ is already pretty good. And I speculate that their next move will be to note that $p^2 + 1 leq p^3$ (for $p geq 3$)so that we can write:
[all the previous stuff] $leq p^3 + p^3 + p^3$.
Now we are in a position to apply the Induction Hypothesis to obtain
[everything we talked about so far] $leq 3^p + 3^p + 3^p$,
from which it is only a small step to the final answer.
answered Apr 16 '17 at 18:45
VincentVincent
3,35611229
$endgroup$
$begingroup$
What? But the right side of the inequality only says 3^n. So why isn't the right side only 3^(p+1)? I dont understand what you mean with they just find a term. Where do they get p^3 + p^3 + p^2 + 1 from?
$endgroup$
– user5846939
Apr 16 '17 at 19:11
$begingroup$
@user5846939 I am solely talking about the in equality at the top of this answer: the one you said you got stuck on when reading your book. When I say left or right hand side I mean the left and right hand side of that inequality, not of the more interesting inequality n^3 leq 3^n$. So both the left hand side and the right hand side have 4 terms and the truth of the inequality follows from the fact that the first on the left is smaller/equal than the first on the right, the second on the left is smaller/equal than the second on the right etc.
$endgroup$
– Vincent
Apr 17 '17 at 20:36
$begingroup$
@user5846939 I updated my answer to include some stuff on what I believe was going on in the minds of the people who wrote your book. I hope this helps
$endgroup$
– Vincent
Apr 17 '17 at 21:59
add a comment |
$begingroup$
This answer only explains the inequality
$$p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
you said your book gives. I won't speculate on how they proceed from there to the full result and/or how you could have circumvented using this inequality altogether. (See some of the other answers for more on that last point.)
What they do is for each term on the left find a term (on the right) that is at least as big. So we really have 4 inequalities:
$$p^3 leq p^3$$
$$3p^2 leq p^3$$
$$3p leq p^2$$
$$1 leq 1$$
I guess the outermost two are obvious. To see why the other two hold, remember that $p^3 = p cdot p^2$ and $p^2 = p cdot p$.
UPDATE: the above explains why the inequality is true, but it dawned on me that perhaps your question is how they came up with the terms on the right hand site in the first place.
The answer is: they want, on the right hand side terms that 'look like' $p^3$ because $p^3$ is something they can handle. The reason for that is that the Induction Hypothesis tells us that $p^3 leq 3^p$, so applying the IH takes us finally away from the world of $p^textrm{something}$ to the desired world of $3^{textrm{some expression in } p}$.
But in order to do that, we need our $p^textrm{something}$ to be in the specific form $p^3$.
Hence replacing two out of four of the annoying terms on the left hand side by the more beloved (because appearing in the IH) $p^3$ is already pretty good. And I speculate that their next move will be to note that $p^2 + 1 leq p^3$ (for $p geq 3$)so that we can write:
[all the previous stuff] $leq p^3 + p^3 + p^3$.
Now we are in a position to apply the Induction Hypothesis to obtain
[everything we talked about so far] $leq 3^p + 3^p + 3^p$,
from which it is only a small step to the final answer.
answered Apr 16 '17 at 18:45
VincentVincent
3,35611229
$endgroup$
$begingroup$
What? But the right side of the inequality only says 3^n. So why isn't the right side only 3^(p+1)? I dont understand what you mean with they just find a term. Where do they get p^3 + p^3 + p^2 + 1 from?
$endgroup$
– user5846939
Apr 16 '17 at 19:11
$begingroup$
@user5846939 I am solely talking about the in equality at the top of this answer: the one you said you got stuck on when reading your book. When I say left or right hand side I mean the left and right hand side of that inequality, not of the more interesting inequality n^3 leq 3^n$. So both the left hand side and the right hand side have 4 terms and the truth of the inequality follows from the fact that the first on the left is smaller/equal than the first on the right, the second on the left is smaller/equal than the second on the right etc.
$endgroup$
– Vincent
Apr 17 '17 at 20:36
$begingroup$
@user5846939 I updated my answer to include some stuff on what I believe was going on in the minds of the people who wrote your book. I hope this helps
$endgroup$
– Vincent
Apr 17 '17 at 21:59
add a comment |
$begingroup$
This answer only explains the inequality
$$p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
you said your book gives. I won't speculate on how they proceed from there to the full result and/or how you could have circumvented using this inequality altogether. (See some of the other answers for more on that last point.)
What they do is for each term on the left find a term (on the right) that is at least as big. So we really have 4 inequalities:
$$p^3 leq p^3$$
$$3p^2 leq p^3$$
$$3p leq p^2$$
$$1 leq 1$$
I guess the outermost two are obvious. To see why the other two hold, remember that $p^3 = p cdot p^2$ and $p^2 = p cdot p$.
UPDATE: the above explains why the inequality is true, but it dawned on me that perhaps your question is how they came up with the terms on the right hand site in the first place.
The answer is: they want, on the right hand side terms that 'look like' $p^3$ because $p^3$ is something they can handle. The reason for that is that the Induction Hypothesis tells us that $p^3 leq 3^p$, so applying the IH takes us finally away from the world of $p^textrm{something}$ to the desired world of $3^{textrm{some expression in } p}$.
But in order to do that, we need our $p^textrm{something}$ to be in the specific form $p^3$.
Hence replacing two out of four of the annoying terms on the left hand side by the more beloved (because appearing in the IH) $p^3$ is already pretty good. And I speculate that their next move will be to note that $p^2 + 1 leq p^3$ (for $p geq 3$)so that we can write:
[all the previous stuff] $leq p^3 + p^3 + p^3$.
Now we are in a position to apply the Induction Hypothesis to obtain
[everything we talked about so far] $leq 3^p + 3^p + 3^p$,
from which it is only a small step to the final answer.
answered Apr 16 '17 at 18:45
VincentVincent
3,35611229
$endgroup$
This answer only explains the inequality
$$p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$
you said your book gives. I won't speculate on how they proceed from there to the full result and/or how you could have circumvented using this inequality altogether. (See some of the other answers for more on that last point.)
What they do is for each term on the left find a term (on the right) that is at least as big. So we really have 4 inequalities:
$$p^3 leq p^3$$
$$3p^2 leq p^3$$
$$3p leq p^2$$
$$1 leq 1$$
I guess the outermost two are obvious. To see why the other two hold, remember that $p^3 = p cdot p^2$ and $p^2 = p cdot p$.
UPDATE: the above explains why the inequality is true, but it dawned on me that perhaps your question is how they came up with the terms on the right hand site in the first place.
The answer is: they want, on the right hand side terms that 'look like' $p^3$ because $p^3$ is something they can handle. The reason for that is that the Induction Hypothesis tells us that $p^3 leq 3^p$, so applying the IH takes us finally away from the world of $p^textrm{something}$ to the desired world of $3^{textrm{some expression in } p}$.
But in order to do that, we need our $p^textrm{something}$ to be in the specific form $p^3$.
Hence replacing two out of four of the annoying terms on the left hand side by the more beloved (because appearing in the IH) $p^3$ is already pretty good. And I speculate that their next move will be to note that $p^2 + 1 leq p^3$ (for $p geq 3$)so that we can write:
[all the previous stuff] $leq p^3 + p^3 + p^3$.
Now we are in a position to apply the Induction Hypothesis to obtain
[everything we talked about so far] $leq 3^p + 3^p + 3^p$,
from which it is only a small step to the final answer.
answered Apr 16 '17 at 18:45
VincentVincent
3,35611229
edited Apr 17 '17 at 21:57
answered Apr 16 '17 at 18:45
VincentVincent
3,35611229
answered Apr 16 '17 at 18:45
VincentVincent
3,35611229
answered Apr 16 '17 at 18:45
VincentVincent
3,35611229
3,35611229
$begingroup$
What? But the right side of the inequality only says 3^n. So why isn't the right side only 3^(p+1)? I dont understand what you mean with they just find a term. Where do they get p^3 + p^3 + p^2 + 1 from?
$endgroup$
– user5846939
Apr 16 '17 at 19:11
$begingroup$
@user5846939 I am solely talking about the in equality at the top of this answer: the one you said you got stuck on when reading your book. When I say left or right hand side I mean the left and right hand side of that inequality, not of the more interesting inequality n^3 leq 3^n$. So both the left hand side and the right hand side have 4 terms and the truth of the inequality follows from the fact that the first on the left is smaller/equal than the first on the right, the second on the left is smaller/equal than the second on the right etc.
$endgroup$
– Vincent
Apr 17 '17 at 20:36
$begingroup$
@user5846939 I updated my answer to include some stuff on what I believe was going on in the minds of the people who wrote your book. I hope this helps
$endgroup$
– Vincent
Apr 17 '17 at 21:59
add a comment |
$begingroup$
What? But the right side of the inequality only says 3^n. So why isn't the right side only 3^(p+1)? I dont understand what you mean with they just find a term. Where do they get p^3 + p^3 + p^2 + 1 from?
$endgroup$
– user5846939
Apr 16 '17 at 19:11
$begingroup$
@user5846939 I am solely talking about the in equality at the top of this answer: the one you said you got stuck on when reading your book. When I say left or right hand side I mean the left and right hand side of that inequality, not of the more interesting inequality n^3 leq 3^n$. So both the left hand side and the right hand side have 4 terms and the truth of the inequality follows from the fact that the first on the left is smaller/equal than the first on the right, the second on the left is smaller/equal than the second on the right etc.
$endgroup$
– Vincent
Apr 17 '17 at 20:36
$begingroup$
@user5846939 I updated my answer to include some stuff on what I believe was going on in the minds of the people who wrote your book. I hope this helps
$endgroup$
– Vincent
Apr 17 '17 at 21:59
$begingroup$
What? But the right side of the inequality only says 3^n. So why isn't the right side only 3^(p+1)? I dont understand what you mean with they just find a term. Where do they get p^3 + p^3 + p^2 + 1 from?
$endgroup$
– user5846939
Apr 16 '17 at 19:11
$begingroup$
What? But the right side of the inequality only says 3^n. So why isn't the right side only 3^(p+1)? I dont understand what you mean with they just find a term. Where do they get p^3 + p^3 + p^2 + 1 from?
$endgroup$
– user5846939
Apr 16 '17 at 19:11
$begingroup$
@user5846939 I am solely talking about the in equality at the top of this answer: the one you said you got stuck on when reading your book. When I say left or right hand side I mean the left and right hand side of that inequality, not of the more interesting inequality n^3 leq 3^n$. So both the left hand side and the right hand side have 4 terms and the truth of the inequality follows from the fact that the first on the left is smaller/equal than the first on the right, the second on the left is smaller/equal than the second on the right etc.
$endgroup$
– Vincent
Apr 17 '17 at 20:36
$begingroup$
@user5846939 I am solely talking about the in equality at the top of this answer: the one you said you got stuck on when reading your book. When I say left or right hand side I mean the left and right hand side of that inequality, not of the more interesting inequality n^3 leq 3^n$. So both the left hand side and the right hand side have 4 terms and the truth of the inequality follows from the fact that the first on the left is smaller/equal than the first on the right, the second on the left is smaller/equal than the second on the right etc.
$endgroup$
– Vincent
Apr 17 '17 at 20:36
$begingroup$
@user5846939 I updated my answer to include some stuff on what I believe was going on in the minds of the people who wrote your book. I hope this helps
$endgroup$
– Vincent
Apr 17 '17 at 21:59
$begingroup$
@user5846939 I updated my answer to include some stuff on what I believe was going on in the minds of the people who wrote your book. I hope this helps
$endgroup$
– Vincent
Apr 17 '17 at 21:59
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.
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%2f2237199%2fprove-by-induction-that-n3-leq-3n-for-all-integers-geq-3%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
1
$begingroup$
Is $p3+p3+p2+1$ supposed to say $p^3+p^3+p^2+1$? If so, then this is because $3p^2 leq pcdot p^2 =p^3$ (since the base case is $p=3$, so certainly $3 leq p$). Similaly $3p leq pcdot p=p^2$.
$endgroup$
– kccu
Apr 16 '17 at 18:38
$begingroup$
Yes I was about to help edit, and I also wondered that part.
$endgroup$
– mathreadler
Apr 16 '17 at 18:39
$begingroup$
By the way welcome to the site. Please consider learning MathJax as it is used for typesetting math. It gets easier to read and increases chances of good responses to questions.
$endgroup$
– mathreadler
Apr 16 '17 at 18:41