Proof of the principle of backwards inductionBackward induction (Tao Analysis vol. 1).Backward induction (Tao Analysis vol. 1).Proof for Strong Induction PrincipleInduction Proof with FactorialsProof of induction principle, Proof falsificationDifference between downward induction and infinite descentMathematical induction from $n=1$Two questions about proof by inductionAm I permitted to use the truth of the base case during the inductive step in a proof using weak induction?Evaluate my proof of strong induction (Analysis I, Tao)Terry Tao's strong induction formulation
My adviser wants to be the first author
I need to drive a 7/16" nut but am unsure how to use the socket I bought for my screwdriver
Do I need life insurance if I can cover my own funeral costs?
Instead of Universal Basic Income, why not Universal Basic NEEDS?
How do anti-virus programs start at Windows boot?
Why does Deadpool say "You're welcome, Canada," after shooting Ryan Reynolds in the end credits?
Is it possible to upcast ritual spells?
Happy pi day, everyone!
Did CPM support custom hardware using device drivers?
Current sense amp + op-amp buffer + ADC: Measuring down to 0 with single supply
How to simplify this time periods definition interface?
Good allowance savings plan?
Should we release the security issues we found in our product as CVE or we can just update those on weekly release notes?
What does it mean to make a bootable LiveUSB?
How can I change step-down my variable input voltage? [Microcontroller]
Does the statement `int val = (++i > ++j) ? ++i : ++j;` invoke undefined behavior?
Make a transparent 448*448 image
What are some nice/clever ways to introduce the tonic's dominant seventh chord?
Theorems like the Lovász Local Lemma?
How could a female member of a species produce eggs unto death?
At what level can a dragon innately cast its spells?
Why are there 40 737 Max planes in flight when they have been grounded as not airworthy?
Ban on all campaign finance?
Professor being mistaken for a grad student
Proof of the principle of backwards induction
Backward induction (Tao Analysis vol. 1).Backward induction (Tao Analysis vol. 1).Proof for Strong Induction PrincipleInduction Proof with FactorialsProof of induction principle, Proof falsificationDifference between downward induction and infinite descentMathematical induction from $n=1$Two questions about proof by inductionAm I permitted to use the truth of the base case during the inductive step in a proof using weak induction?Evaluate my proof of strong induction (Analysis I, Tao)Terry Tao's strong induction formulation
$begingroup$
I have difficulty in neatly writing down a proof for the following:
Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $mleq n$; this is know as the principle of backwards induction. (Hint: apply induction to the variable $n$.)
First of all, I am unsure about what the base case should look like. For the induction step, I understand that if we suppose inductively that $P(n)$ is true, that then for a natural number $a$ s.t. $a++=n$ it holds that $P(a)$ is true, and then for a natural number $b$ s.t. $b++=a$ it holds that $P(b)$ is true etc. Hence for all natural numbers $mleq n$, $P(m)$ is true.
Could anyone please tell me what the base case should look like, and whether there is a neater way of writing down the induction step?
elementary-set-theory induction
edited Jul 31 '13 at 18:06
Stefan Hamcke
21.8k42880
asked Jul 31 '13 at 17:43
dreamerdreamer
1,68143062
$endgroup$
|
show 4 more comments
$begingroup$
I have difficulty in neatly writing down a proof for the following:
Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $mleq n$; this is know as the principle of backwards induction. (Hint: apply induction to the variable $n$.)
First of all, I am unsure about what the base case should look like. For the induction step, I understand that if we suppose inductively that $P(n)$ is true, that then for a natural number $a$ s.t. $a++=n$ it holds that $P(a)$ is true, and then for a natural number $b$ s.t. $b++=a$ it holds that $P(b)$ is true etc. Hence for all natural numbers $mleq n$, $P(m)$ is true.
Could anyone please tell me what the base case should look like, and whether there is a neater way of writing down the induction step?
elementary-set-theory induction
edited Jul 31 '13 at 18:06
Stefan Hamcke
21.8k42880
asked Jul 31 '13 at 17:43
dreamerdreamer
1,68143062
$endgroup$
$begingroup$
Seems to me that the hint is a little misleading. The way I would approach this is try to prove that for any $a leq n$, $P(m)$ is true for all natural numbers $n - a leq m leq n$, by induction on $a$.
$endgroup$
– Scaramouche
Jul 31 '13 at 17:46
2
$begingroup$
What does $a++=n$ mean?
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 17:52
$begingroup$
This question was asked the other day (or at least a very similar question), see here.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:00
$begingroup$
I also believe that rbm is reading from Tao's analysis where he uses $++$ to represent the successor when constructing $BbbN$ from the Peano axioms.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:04
1
$begingroup$
Using $++$ is by all means a horrible mathematical notation. In particular since $+$ itself is already in the language and is a binary operator. Using $s$ or $S$ is much clearer and common enough, at least in logic.
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 18:29
|
show 4 more comments
$begingroup$
I have difficulty in neatly writing down a proof for the following:
Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $mleq n$; this is know as the principle of backwards induction. (Hint: apply induction to the variable $n$.)
First of all, I am unsure about what the base case should look like. For the induction step, I understand that if we suppose inductively that $P(n)$ is true, that then for a natural number $a$ s.t. $a++=n$ it holds that $P(a)$ is true, and then for a natural number $b$ s.t. $b++=a$ it holds that $P(b)$ is true etc. Hence for all natural numbers $mleq n$, $P(m)$ is true.
Could anyone please tell me what the base case should look like, and whether there is a neater way of writing down the induction step?
elementary-set-theory induction
edited Jul 31 '13 at 18:06
Stefan Hamcke
21.8k42880
asked Jul 31 '13 at 17:43
dreamerdreamer
1,68143062
$endgroup$
I have difficulty in neatly writing down a proof for the following:
Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $mleq n$; this is know as the principle of backwards induction. (Hint: apply induction to the variable $n$.)
First of all, I am unsure about what the base case should look like. For the induction step, I understand that if we suppose inductively that $P(n)$ is true, that then for a natural number $a$ s.t. $a++=n$ it holds that $P(a)$ is true, and then for a natural number $b$ s.t. $b++=a$ it holds that $P(b)$ is true etc. Hence for all natural numbers $mleq n$, $P(m)$ is true.
Could anyone please tell me what the base case should look like, and whether there is a neater way of writing down the induction step?
elementary-set-theory induction
elementary-set-theory induction
edited Jul 31 '13 at 18:06
Stefan Hamcke
21.8k42880
asked Jul 31 '13 at 17:43
dreamerdreamer
1,68143062
edited Jul 31 '13 at 18:06
Stefan Hamcke
21.8k42880
asked Jul 31 '13 at 17:43
dreamerdreamer
1,68143062
edited Jul 31 '13 at 18:06
Stefan Hamcke
21.8k42880
edited Jul 31 '13 at 18:06
Stefan Hamcke
21.8k42880
edited Jul 31 '13 at 18:06
Stefan Hamcke
21.8k42880
21.8k42880
asked Jul 31 '13 at 17:43
dreamerdreamer
1,68143062
asked Jul 31 '13 at 17:43
dreamerdreamer
1,68143062
asked Jul 31 '13 at 17:43
dreamerdreamer
1,68143062
1,68143062
$begingroup$
Seems to me that the hint is a little misleading. The way I would approach this is try to prove that for any $a leq n$, $P(m)$ is true for all natural numbers $n - a leq m leq n$, by induction on $a$.
$endgroup$
– Scaramouche
Jul 31 '13 at 17:46
2
$begingroup$
What does $a++=n$ mean?
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 17:52
$begingroup$
This question was asked the other day (or at least a very similar question), see here.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:00
$begingroup$
I also believe that rbm is reading from Tao's analysis where he uses $++$ to represent the successor when constructing $BbbN$ from the Peano axioms.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:04
1
$begingroup$
Using $++$ is by all means a horrible mathematical notation. In particular since $+$ itself is already in the language and is a binary operator. Using $s$ or $S$ is much clearer and common enough, at least in logic.
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 18:29
|
show 4 more comments
$begingroup$
Seems to me that the hint is a little misleading. The way I would approach this is try to prove that for any $a leq n$, $P(m)$ is true for all natural numbers $n - a leq m leq n$, by induction on $a$.
$endgroup$
– Scaramouche
Jul 31 '13 at 17:46
2
$begingroup$
What does $a++=n$ mean?
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 17:52
$begingroup$
This question was asked the other day (or at least a very similar question), see here.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:00
$begingroup$
I also believe that rbm is reading from Tao's analysis where he uses $++$ to represent the successor when constructing $BbbN$ from the Peano axioms.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:04
1
$begingroup$
Using $++$ is by all means a horrible mathematical notation. In particular since $+$ itself is already in the language and is a binary operator. Using $s$ or $S$ is much clearer and common enough, at least in logic.
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 18:29
$begingroup$
Seems to me that the hint is a little misleading. The way I would approach this is try to prove that for any $a leq n$, $P(m)$ is true for all natural numbers $n - a leq m leq n$, by induction on $a$.
$endgroup$
– Scaramouche
Jul 31 '13 at 17:46
$begingroup$
Seems to me that the hint is a little misleading. The way I would approach this is try to prove that for any $a leq n$, $P(m)$ is true for all natural numbers $n - a leq m leq n$, by induction on $a$.
$endgroup$
– Scaramouche
Jul 31 '13 at 17:46
2
2
$begingroup$
What does $a++=n$ mean?
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 17:52
$begingroup$
What does $a++=n$ mean?
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 17:52
$begingroup$
This question was asked the other day (or at least a very similar question), see here.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:00
$begingroup$
This question was asked the other day (or at least a very similar question), see here.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:00
$begingroup$
I also believe that rbm is reading from Tao's analysis where he uses $++$ to represent the successor when constructing $BbbN$ from the Peano axioms.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:04
$begingroup$
I also believe that rbm is reading from Tao's analysis where he uses $++$ to represent the successor when constructing $BbbN$ from the Peano axioms.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:04
1
1
$begingroup$
Using $++$ is by all means a horrible mathematical notation. In particular since $+$ itself is already in the language and is a binary operator. Using $s$ or $S$ is much clearer and common enough, at least in logic.
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 18:29
$begingroup$
Using $++$ is by all means a horrible mathematical notation. In particular since $+$ itself is already in the language and is a binary operator. Using $s$ or $S$ is much clearer and common enough, at least in logic.
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 18:29
|
show 4 more comments
3 Answers
3
active
oldest
votes
$begingroup$
This answer is to show the statement can be proved on (upward) induction on $n$, as in the hint.
Suppose the statement holds at a specific $n$. The statement of it for $n++$ is then:
Suppose $P(n++)$ is true, then it follows that $P(m)$ holds for all $m le n++.$
From the assumption that $P(n++) implies P(n),$ we arrive at $P(n)$ true, so that from the inductive hypothesis $P(k)$ holds for all $k le n$. Together with the assumption that $P(n++)$ holds, we have the desired conclusion of the inductive step, i.e. that $P(m)$ holds for all $m le n++.$
answered Jul 31 '13 at 18:37
coffeemathcoffeemath
27.3k22342
$endgroup$
$begingroup$
Great! Thanks a lot!
$endgroup$
– dreamer
Jul 31 '13 at 19:41
$begingroup$
One question that came up, what would you say is the base case (did you include that in your answer)?
$endgroup$
– dreamer
Aug 1 '13 at 9:58
1
$begingroup$
@rbm No I didn't since it seems too obvious. It would just say (for $n=1$): Suppose $P(1)$ holds. Then $P(m)$ holds for all $m le 1$. But there's only one such $m$, namely $1$, so that there is nothing to show for the base case.
$endgroup$
– coffeemath
Aug 1 '13 at 11:04
add a comment |
$begingroup$
Prove, by ordinary induction on $k$, the statement "if $n-kgeq0$ then $P(n-k)$. The base case is $P(n)$, and the induction step, going from $k$ to $k+1$, comes from the "backward induction" hypothesis, because increasing $k$ decreases $n-k$.
answered Jul 31 '13 at 18:22
Andreas BlassAndreas Blass
50.2k452109
$endgroup$
$begingroup$
Thank you for your help! That is a nice way of converting it to an ordinary induction problem. One question that I have; how exactly does the base case work (why would $P(n)$ hold true)?
$endgroup$
– dreamer
Jul 31 '13 at 18:29
1
$begingroup$
@rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true."
$endgroup$
– Andreas Blass
Jul 31 '13 at 18:43
$begingroup$
It seems that assuming well-ordering of the naturals, it's quite easy for students to prove variants of standard induction (complete, backward, forward-backward...). But to show that these variants hold using standard induction requires students to modify the proposition to be proved (in your case, it's $n-k geq 0 implies P(n-k)$), which students find difficult. Any tips and ideas that students can practise and use to improve this skill?
$endgroup$
– Maxis Jaisi
Mar 3 '17 at 6:54
add a comment |
$begingroup$
Proof: Let $n in mathbbN$. Using induction on $n$, for the base case $n = 0$, we need to show that $P(m)$ is true $forall mle 0$. But only $0le 0$ so we just need to show that $P(0)$ is true. Since $P(n)$ is true from the hypothesis, $P(0)$ is true and that completes the base case.
Suppose inductively that the principle if true for $n$, i.e $P$ is such that $P(n)$ is true, and whenever $P(m++)$ is true, $P(m)$ is true $forall mle n$. We have to show the principle is true for $n++$ i.e we need to show that $P(m)$ is true $forall mle n++$ given that $P(n++)$ is true and given that whenever $P(m++)$ is true, $P(m)$ is true.
Since $P(n++)$ is true, then $P(n)$ is also true. So we have to show that $P(m)$ is true $m<n$. But from the inductive hypothesis, $P(m)$ is true $forall$ $mle n$ and that completes the induction. $square$
answered Mar 11 at 9:49
Segun OjoSegun Ojo
11
New contributor
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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
);
);
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%2f456589%2fproof-of-the-principle-of-backwards-induction%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$
This answer is to show the statement can be proved on (upward) induction on $n$, as in the hint.
Suppose the statement holds at a specific $n$. The statement of it for $n++$ is then:
Suppose $P(n++)$ is true, then it follows that $P(m)$ holds for all $m le n++.$
From the assumption that $P(n++) implies P(n),$ we arrive at $P(n)$ true, so that from the inductive hypothesis $P(k)$ holds for all $k le n$. Together with the assumption that $P(n++)$ holds, we have the desired conclusion of the inductive step, i.e. that $P(m)$ holds for all $m le n++.$
answered Jul 31 '13 at 18:37
coffeemathcoffeemath
27.3k22342
$endgroup$
$begingroup$
Great! Thanks a lot!
$endgroup$
– dreamer
Jul 31 '13 at 19:41
$begingroup$
One question that came up, what would you say is the base case (did you include that in your answer)?
$endgroup$
– dreamer
Aug 1 '13 at 9:58
1
$begingroup$
@rbm No I didn't since it seems too obvious. It would just say (for $n=1$): Suppose $P(1)$ holds. Then $P(m)$ holds for all $m le 1$. But there's only one such $m$, namely $1$, so that there is nothing to show for the base case.
$endgroup$
– coffeemath
Aug 1 '13 at 11:04
add a comment |
$begingroup$
This answer is to show the statement can be proved on (upward) induction on $n$, as in the hint.
Suppose the statement holds at a specific $n$. The statement of it for $n++$ is then:
Suppose $P(n++)$ is true, then it follows that $P(m)$ holds for all $m le n++.$
From the assumption that $P(n++) implies P(n),$ we arrive at $P(n)$ true, so that from the inductive hypothesis $P(k)$ holds for all $k le n$. Together with the assumption that $P(n++)$ holds, we have the desired conclusion of the inductive step, i.e. that $P(m)$ holds for all $m le n++.$
answered Jul 31 '13 at 18:37
coffeemathcoffeemath
27.3k22342
$endgroup$
$begingroup$
Great! Thanks a lot!
$endgroup$
– dreamer
Jul 31 '13 at 19:41
$begingroup$
One question that came up, what would you say is the base case (did you include that in your answer)?
$endgroup$
– dreamer
Aug 1 '13 at 9:58
1
$begingroup$
@rbm No I didn't since it seems too obvious. It would just say (for $n=1$): Suppose $P(1)$ holds. Then $P(m)$ holds for all $m le 1$. But there's only one such $m$, namely $1$, so that there is nothing to show for the base case.
$endgroup$
– coffeemath
Aug 1 '13 at 11:04
add a comment |
$begingroup$
This answer is to show the statement can be proved on (upward) induction on $n$, as in the hint.
Suppose the statement holds at a specific $n$. The statement of it for $n++$ is then:
Suppose $P(n++)$ is true, then it follows that $P(m)$ holds for all $m le n++.$
From the assumption that $P(n++) implies P(n),$ we arrive at $P(n)$ true, so that from the inductive hypothesis $P(k)$ holds for all $k le n$. Together with the assumption that $P(n++)$ holds, we have the desired conclusion of the inductive step, i.e. that $P(m)$ holds for all $m le n++.$
answered Jul 31 '13 at 18:37
coffeemathcoffeemath
27.3k22342
$endgroup$
This answer is to show the statement can be proved on (upward) induction on $n$, as in the hint.
Suppose the statement holds at a specific $n$. The statement of it for $n++$ is then:
Suppose $P(n++)$ is true, then it follows that $P(m)$ holds for all $m le n++.$
From the assumption that $P(n++) implies P(n),$ we arrive at $P(n)$ true, so that from the inductive hypothesis $P(k)$ holds for all $k le n$. Together with the assumption that $P(n++)$ holds, we have the desired conclusion of the inductive step, i.e. that $P(m)$ holds for all $m le n++.$
answered Jul 31 '13 at 18:37
coffeemathcoffeemath
27.3k22342
answered Jul 31 '13 at 18:37
coffeemathcoffeemath
27.3k22342
answered Jul 31 '13 at 18:37
coffeemathcoffeemath
27.3k22342
answered Jul 31 '13 at 18:37
coffeemathcoffeemath
27.3k22342
27.3k22342
$begingroup$
Great! Thanks a lot!
$endgroup$
– dreamer
Jul 31 '13 at 19:41
$begingroup$
One question that came up, what would you say is the base case (did you include that in your answer)?
$endgroup$
– dreamer
Aug 1 '13 at 9:58
1
$begingroup$
@rbm No I didn't since it seems too obvious. It would just say (for $n=1$): Suppose $P(1)$ holds. Then $P(m)$ holds for all $m le 1$. But there's only one such $m$, namely $1$, so that there is nothing to show for the base case.
$endgroup$
– coffeemath
Aug 1 '13 at 11:04
add a comment |
$begingroup$
Great! Thanks a lot!
$endgroup$
– dreamer
Jul 31 '13 at 19:41
$begingroup$
One question that came up, what would you say is the base case (did you include that in your answer)?
$endgroup$
– dreamer
Aug 1 '13 at 9:58
1
$begingroup$
@rbm No I didn't since it seems too obvious. It would just say (for $n=1$): Suppose $P(1)$ holds. Then $P(m)$ holds for all $m le 1$. But there's only one such $m$, namely $1$, so that there is nothing to show for the base case.
$endgroup$
– coffeemath
Aug 1 '13 at 11:04
$begingroup$
Great! Thanks a lot!
$endgroup$
– dreamer
Jul 31 '13 at 19:41
$begingroup$
Great! Thanks a lot!
$endgroup$
– dreamer
Jul 31 '13 at 19:41
$begingroup$
One question that came up, what would you say is the base case (did you include that in your answer)?
$endgroup$
– dreamer
Aug 1 '13 at 9:58
$begingroup$
One question that came up, what would you say is the base case (did you include that in your answer)?
$endgroup$
– dreamer
Aug 1 '13 at 9:58
1
1
$begingroup$
@rbm No I didn't since it seems too obvious. It would just say (for $n=1$): Suppose $P(1)$ holds. Then $P(m)$ holds for all $m le 1$. But there's only one such $m$, namely $1$, so that there is nothing to show for the base case.
$endgroup$
– coffeemath
Aug 1 '13 at 11:04
$begingroup$
@rbm No I didn't since it seems too obvious. It would just say (for $n=1$): Suppose $P(1)$ holds. Then $P(m)$ holds for all $m le 1$. But there's only one such $m$, namely $1$, so that there is nothing to show for the base case.
$endgroup$
– coffeemath
Aug 1 '13 at 11:04
add a comment |
$begingroup$
Prove, by ordinary induction on $k$, the statement "if $n-kgeq0$ then $P(n-k)$. The base case is $P(n)$, and the induction step, going from $k$ to $k+1$, comes from the "backward induction" hypothesis, because increasing $k$ decreases $n-k$.
answered Jul 31 '13 at 18:22
Andreas BlassAndreas Blass
50.2k452109
$endgroup$
$begingroup$
Thank you for your help! That is a nice way of converting it to an ordinary induction problem. One question that I have; how exactly does the base case work (why would $P(n)$ hold true)?
$endgroup$
– dreamer
Jul 31 '13 at 18:29
1
$begingroup$
@rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true."
$endgroup$
– Andreas Blass
Jul 31 '13 at 18:43
$begingroup$
It seems that assuming well-ordering of the naturals, it's quite easy for students to prove variants of standard induction (complete, backward, forward-backward...). But to show that these variants hold using standard induction requires students to modify the proposition to be proved (in your case, it's $n-k geq 0 implies P(n-k)$), which students find difficult. Any tips and ideas that students can practise and use to improve this skill?
$endgroup$
– Maxis Jaisi
Mar 3 '17 at 6:54
add a comment |
$begingroup$
Prove, by ordinary induction on $k$, the statement "if $n-kgeq0$ then $P(n-k)$. The base case is $P(n)$, and the induction step, going from $k$ to $k+1$, comes from the "backward induction" hypothesis, because increasing $k$ decreases $n-k$.
answered Jul 31 '13 at 18:22
Andreas BlassAndreas Blass
50.2k452109
$endgroup$
$begingroup$
Thank you for your help! That is a nice way of converting it to an ordinary induction problem. One question that I have; how exactly does the base case work (why would $P(n)$ hold true)?
$endgroup$
– dreamer
Jul 31 '13 at 18:29
1
$begingroup$
@rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true."
$endgroup$
– Andreas Blass
Jul 31 '13 at 18:43
$begingroup$
It seems that assuming well-ordering of the naturals, it's quite easy for students to prove variants of standard induction (complete, backward, forward-backward...). But to show that these variants hold using standard induction requires students to modify the proposition to be proved (in your case, it's $n-k geq 0 implies P(n-k)$), which students find difficult. Any tips and ideas that students can practise and use to improve this skill?
$endgroup$
– Maxis Jaisi
Mar 3 '17 at 6:54
add a comment |
$begingroup$
Prove, by ordinary induction on $k$, the statement "if $n-kgeq0$ then $P(n-k)$. The base case is $P(n)$, and the induction step, going from $k$ to $k+1$, comes from the "backward induction" hypothesis, because increasing $k$ decreases $n-k$.
answered Jul 31 '13 at 18:22
Andreas BlassAndreas Blass
50.2k452109
$endgroup$
Prove, by ordinary induction on $k$, the statement "if $n-kgeq0$ then $P(n-k)$. The base case is $P(n)$, and the induction step, going from $k$ to $k+1$, comes from the "backward induction" hypothesis, because increasing $k$ decreases $n-k$.
answered Jul 31 '13 at 18:22
Andreas BlassAndreas Blass
50.2k452109
answered Jul 31 '13 at 18:22
Andreas BlassAndreas Blass
50.2k452109
answered Jul 31 '13 at 18:22
Andreas BlassAndreas Blass
50.2k452109
answered Jul 31 '13 at 18:22
Andreas BlassAndreas Blass
50.2k452109
50.2k452109
$begingroup$
Thank you for your help! That is a nice way of converting it to an ordinary induction problem. One question that I have; how exactly does the base case work (why would $P(n)$ hold true)?
$endgroup$
– dreamer
Jul 31 '13 at 18:29
1
$begingroup$
@rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true."
$endgroup$
– Andreas Blass
Jul 31 '13 at 18:43
$begingroup$
It seems that assuming well-ordering of the naturals, it's quite easy for students to prove variants of standard induction (complete, backward, forward-backward...). But to show that these variants hold using standard induction requires students to modify the proposition to be proved (in your case, it's $n-k geq 0 implies P(n-k)$), which students find difficult. Any tips and ideas that students can practise and use to improve this skill?
$endgroup$
– Maxis Jaisi
Mar 3 '17 at 6:54
add a comment |
$begingroup$
Thank you for your help! That is a nice way of converting it to an ordinary induction problem. One question that I have; how exactly does the base case work (why would $P(n)$ hold true)?
$endgroup$
– dreamer
Jul 31 '13 at 18:29
1
$begingroup$
@rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true."
$endgroup$
– Andreas Blass
Jul 31 '13 at 18:43
$begingroup$
It seems that assuming well-ordering of the naturals, it's quite easy for students to prove variants of standard induction (complete, backward, forward-backward...). But to show that these variants hold using standard induction requires students to modify the proposition to be proved (in your case, it's $n-k geq 0 implies P(n-k)$), which students find difficult. Any tips and ideas that students can practise and use to improve this skill?
$endgroup$
– Maxis Jaisi
Mar 3 '17 at 6:54
$begingroup$
Thank you for your help! That is a nice way of converting it to an ordinary induction problem. One question that I have; how exactly does the base case work (why would $P(n)$ hold true)?
$endgroup$
– dreamer
Jul 31 '13 at 18:29
$begingroup$
Thank you for your help! That is a nice way of converting it to an ordinary induction problem. One question that I have; how exactly does the base case work (why would $P(n)$ hold true)?
$endgroup$
– dreamer
Jul 31 '13 at 18:29
1
1
$begingroup$
@rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true."
$endgroup$
– Andreas Blass
Jul 31 '13 at 18:43
$begingroup$
@rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true."
$endgroup$
– Andreas Blass
Jul 31 '13 at 18:43
$begingroup$
It seems that assuming well-ordering of the naturals, it's quite easy for students to prove variants of standard induction (complete, backward, forward-backward...). But to show that these variants hold using standard induction requires students to modify the proposition to be proved (in your case, it's $n-k geq 0 implies P(n-k)$), which students find difficult. Any tips and ideas that students can practise and use to improve this skill?
$endgroup$
– Maxis Jaisi
Mar 3 '17 at 6:54
$begingroup$
It seems that assuming well-ordering of the naturals, it's quite easy for students to prove variants of standard induction (complete, backward, forward-backward...). But to show that these variants hold using standard induction requires students to modify the proposition to be proved (in your case, it's $n-k geq 0 implies P(n-k)$), which students find difficult. Any tips and ideas that students can practise and use to improve this skill?
$endgroup$
– Maxis Jaisi
Mar 3 '17 at 6:54
add a comment |
$begingroup$
Proof: Let $n in mathbbN$. Using induction on $n$, for the base case $n = 0$, we need to show that $P(m)$ is true $forall mle 0$. But only $0le 0$ so we just need to show that $P(0)$ is true. Since $P(n)$ is true from the hypothesis, $P(0)$ is true and that completes the base case.
Suppose inductively that the principle if true for $n$, i.e $P$ is such that $P(n)$ is true, and whenever $P(m++)$ is true, $P(m)$ is true $forall mle n$. We have to show the principle is true for $n++$ i.e we need to show that $P(m)$ is true $forall mle n++$ given that $P(n++)$ is true and given that whenever $P(m++)$ is true, $P(m)$ is true.
Since $P(n++)$ is true, then $P(n)$ is also true. So we have to show that $P(m)$ is true $m<n$. But from the inductive hypothesis, $P(m)$ is true $forall$ $mle n$ and that completes the induction. $square$
answered Mar 11 at 9:49
Segun OjoSegun Ojo
11
New contributor
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Proof: Let $n in mathbbN$. Using induction on $n$, for the base case $n = 0$, we need to show that $P(m)$ is true $forall mle 0$. But only $0le 0$ so we just need to show that $P(0)$ is true. Since $P(n)$ is true from the hypothesis, $P(0)$ is true and that completes the base case.
Suppose inductively that the principle if true for $n$, i.e $P$ is such that $P(n)$ is true, and whenever $P(m++)$ is true, $P(m)$ is true $forall mle n$. We have to show the principle is true for $n++$ i.e we need to show that $P(m)$ is true $forall mle n++$ given that $P(n++)$ is true and given that whenever $P(m++)$ is true, $P(m)$ is true.
Since $P(n++)$ is true, then $P(n)$ is also true. So we have to show that $P(m)$ is true $m<n$. But from the inductive hypothesis, $P(m)$ is true $forall$ $mle n$ and that completes the induction. $square$
answered Mar 11 at 9:49
Segun OjoSegun Ojo
11
New contributor
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Proof: Let $n in mathbbN$. Using induction on $n$, for the base case $n = 0$, we need to show that $P(m)$ is true $forall mle 0$. But only $0le 0$ so we just need to show that $P(0)$ is true. Since $P(n)$ is true from the hypothesis, $P(0)$ is true and that completes the base case.
Suppose inductively that the principle if true for $n$, i.e $P$ is such that $P(n)$ is true, and whenever $P(m++)$ is true, $P(m)$ is true $forall mle n$. We have to show the principle is true for $n++$ i.e we need to show that $P(m)$ is true $forall mle n++$ given that $P(n++)$ is true and given that whenever $P(m++)$ is true, $P(m)$ is true.
Since $P(n++)$ is true, then $P(n)$ is also true. So we have to show that $P(m)$ is true $m<n$. But from the inductive hypothesis, $P(m)$ is true $forall$ $mle n$ and that completes the induction. $square$
answered Mar 11 at 9:49
Segun OjoSegun Ojo
11
New contributor
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Proof: Let $n in mathbbN$. Using induction on $n$, for the base case $n = 0$, we need to show that $P(m)$ is true $forall mle 0$. But only $0le 0$ so we just need to show that $P(0)$ is true. Since $P(n)$ is true from the hypothesis, $P(0)$ is true and that completes the base case.
Suppose inductively that the principle if true for $n$, i.e $P$ is such that $P(n)$ is true, and whenever $P(m++)$ is true, $P(m)$ is true $forall mle n$. We have to show the principle is true for $n++$ i.e we need to show that $P(m)$ is true $forall mle n++$ given that $P(n++)$ is true and given that whenever $P(m++)$ is true, $P(m)$ is true.
Since $P(n++)$ is true, then $P(n)$ is also true. So we have to show that $P(m)$ is true $m<n$. But from the inductive hypothesis, $P(m)$ is true $forall$ $mle n$ and that completes the induction. $square$
answered Mar 11 at 9:49
Segun OjoSegun Ojo
11
New contributor
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Mar 11 at 9:49
Segun OjoSegun Ojo
11
New contributor
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Mar 11 at 9:49
Segun OjoSegun Ojo
11
answered Mar 11 at 9:49
Segun OjoSegun Ojo
11
11
New contributor
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Segun Ojo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
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%2f456589%2fproof-of-the-principle-of-backwards-induction%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
$begingroup$
Seems to me that the hint is a little misleading. The way I would approach this is try to prove that for any $a leq n$, $P(m)$ is true for all natural numbers $n - a leq m leq n$, by induction on $a$.
$endgroup$
– Scaramouche
Jul 31 '13 at 17:46
2
$begingroup$
What does $a++=n$ mean?
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 17:52
$begingroup$
This question was asked the other day (or at least a very similar question), see here.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:00
$begingroup$
I also believe that rbm is reading from Tao's analysis where he uses $++$ to represent the successor when constructing $BbbN$ from the Peano axioms.
$endgroup$
– Kenny Hegeland
Jul 31 '13 at 18:04
1
$begingroup$
Using $++$ is by all means a horrible mathematical notation. In particular since $+$ itself is already in the language and is a binary operator. Using $s$ or $S$ is much clearer and common enough, at least in logic.
$endgroup$
– Asaf Karagila♦
Jul 31 '13 at 18:29