<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@c9d8957b4d5d40ea83854b91131e0523" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Introduction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@37005ab18bf24f0b9d7a941c5932b5de">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@37005ab18bf24f0b9d7a941c5932b5de" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Read <a href="/assets/courseware/v1/34733a5c856b4bd0a156471dba4a304a/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Session8.pdf" target="[object Object]">Chapter 5.1–5.3 (PDF</a>) of <em>Mathematics for Computer Science</em> for 1.8 Induction.</p>
<p>View the <a href="/assets/courseware/v1/0e35e888cf416aa729f9177abb0a70c1/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_cp8.pdf" target="[object Object]">Section 1.8 In-Class Questions (PDF)</a> </p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@6bd85294781d4bd492be682cd15cec69" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Induction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@40dd131b13c342e68feefeb89ce68351">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@40dd131b13c342e68feefeb89ce68351" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Induction</h3>
<div
id="video_40dd131b13c342e68feefeb89ce68351"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:XnV8GAuAqJM", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@40dd131b13c342e68feefeb89ce68351/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@40dd131b13c342e68feefeb89ce68351/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_induction_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@40dd131b13c342e68feefeb89ce68351/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@40dd131b13c342e68feefeb89ce68351/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="40dd131b13c342e68feefeb89ce68351"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_40dd131b13c342e68feefeb89ce68351">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_40dd131b13c342e68feefeb89ce68351">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_induction_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@40dd131b13c342e68feefeb89ce68351/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@40dd131b13c342e68feefeb89ce68351/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@30bc9cb9ced848289dd363a976725a91">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@30bc9cb9ced848289dd363a976725a91" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/8b499319854da124e770a8c29af69eb6/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS16_Induction.pdf" target="[object Object]">Induction (PDF)</a></p>
<p><a href="/assets/courseware/v1/ec1cda724ec3d52bd846a4b42e7b6ed3/asset-v1:OCW+6.042J+2T2019+type@asset+block/Induction_1.8_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@035804f882c44198bc30798e1a0c9129" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Bogus Induction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@9a270dcfb3624c7f8195549164268023">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@9a270dcfb3624c7f8195549164268023" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Bogus Induction</h3>
<div
id="video_9a270dcfb3624c7f8195549164268023"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:D3E5CKebKuQ", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@9a270dcfb3624c7f8195549164268023/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@9a270dcfb3624c7f8195549164268023/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia600207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_bogusinduction_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@9a270dcfb3624c7f8195549164268023/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@9a270dcfb3624c7f8195549164268023/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="9a270dcfb3624c7f8195549164268023"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_9a270dcfb3624c7f8195549164268023">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_9a270dcfb3624c7f8195549164268023">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia600207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_bogusinduction_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@9a270dcfb3624c7f8195549164268023/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@9a270dcfb3624c7f8195549164268023/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@7c8b35eb4529406eb9373183a3cea7c1">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@7c8b35eb4529406eb9373183a3cea7c1" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/95fc0efdaa03ca4314a3f729295a8177/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS16_BogusInductn.pdf" target="[object Object]">Bogus Induction (PDF)</a></p>
<p><a href="/assets/courseware/v1/06f678086c3fbf8fbccd075e9ea64be7/asset-v1:OCW+6.042J+2T2019+type@asset+block/BogusInduction_1.8_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@3a39269778d44e8dafa9586dddb7e0c9" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Same Colored Horses</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@01296584189849648f5ff10b4abb7077">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@01296584189849648f5ff10b4abb7077" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01296584189849648f5ff10b4abb7077" class="problems-wrapper" role="group"
aria-labelledby="01296584189849648f5ff10b4abb7077-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@01296584189849648f5ff10b4abb7077" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@01296584189849648f5ff10b4abb7077/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01296584189849648f5ff10b4abb7077-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@01296584189849648f5ff10b4abb7077-problem-progress" tabindex="-1">
Same Colored Horses
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@01296584189849648f5ff10b4abb7077-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p> <p>In the bogus induction proof that all horses are of the same color, where does the induction break down and why?</p></p>
<div class="choicegroup capa_inputtype" id="inputtype_01296584189849648f5ff10b4abb7077_2_1">
<fieldset aria-describedby="status_01296584189849648f5ff10b4abb7077_2_1">
<div class="field">
<input type="radio" name="input_01296584189849648f5ff10b4abb7077_2_1" id="input_01296584189849648f5ff10b4abb7077_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="01296584189849648f5ff10b4abb7077_2_1-choice_0-label" for="input_01296584189849648f5ff10b4abb7077_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01296584189849648f5ff10b4abb7077_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo></math>, because the base case should be <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo></math>
</label>
</div>
<div class="field">
<input type="radio" name="input_01296584189849648f5ff10b4abb7077_2_1" id="input_01296584189849648f5ff10b4abb7077_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="01296584189849648f5ff10b4abb7077_2_1-choice_1-label" for="input_01296584189849648f5ff10b4abb7077_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01296584189849648f5ff10b4abb7077_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo stretchy="false">&#8594;<!-- &#8594; --></mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
</math> because there are no middle horses when <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>=</mo>
<mn>2</mn>
</math>
</label>
</div>
<div class="field">
<input type="radio" name="input_01296584189849648f5ff10b4abb7077_2_1" id="input_01296584189849648f5ff10b4abb7077_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="01296584189849648f5ff10b4abb7077_2_1-choice_2-label" for="input_01296584189849648f5ff10b4abb7077_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01296584189849648f5ff10b4abb7077_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo stretchy="false">&#8594;<!-- &#8594; --></mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>3</mn>
<mo stretchy="false">)</mo>
</math>, because there is only one middle horse
</label>
</div>
<div class="field">
<input type="radio" name="input_01296584189849648f5ff10b4abb7077_2_1" id="input_01296584189849648f5ff10b4abb7077_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="01296584189849648f5ff10b4abb7077_2_1-choice_3-label" for="input_01296584189849648f5ff10b4abb7077_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01296584189849648f5ff10b4abb7077_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>n</mn>
<mo stretchy="false">)</mo>
<mo stretchy="false">&#8594;<!-- &#8594; --></mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>n+1</mn>
<mo stretchy="false">)</mo>
</math>for <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo>&#8805;<!-- &#8805; --></mo>
</math> 3, because the order of the horses is important
</label>
</div>
<span id="answer_01296584189849648f5ff10b4abb7077_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01296584189849648f5ff10b4abb7077_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Same Colored Horses" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01296584189849648f5ff10b4abb7077" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01296584189849648f5ff10b4abb7077">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="01296584189849648f5ff10b4abb7077-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01296584189849648f5ff10b4abb7077-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01296584189849648f5ff10b4abb7077-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01296584189849648f5ff10b4abb7077-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@06517d131f3f438fa6ffb5f211572e30" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Strong Induction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@42341dfbdbb2492d89505b402a47ff94">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@42341dfbdbb2492d89505b402a47ff94" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Strong Induction</h3>
<div
id="video_42341dfbdbb2492d89505b402a47ff94"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:TUueMeRooBk", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@42341dfbdbb2492d89505b402a47ff94/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@42341dfbdbb2492d89505b402a47ff94/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_stronginduction_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@42341dfbdbb2492d89505b402a47ff94/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@42341dfbdbb2492d89505b402a47ff94/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="42341dfbdbb2492d89505b402a47ff94"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_42341dfbdbb2492d89505b402a47ff94">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_42341dfbdbb2492d89505b402a47ff94">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_stronginduction_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@42341dfbdbb2492d89505b402a47ff94/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@42341dfbdbb2492d89505b402a47ff94/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@67461a6e7fba4ffda07b29f7424d5274">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@67461a6e7fba4ffda07b29f7424d5274" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/720a1129c146f6423b9ff61c298996e1/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS16_StrongInduct.pdf" target="[object Object]">Strong Induction (PDF)</a></p>
<p><a href="/assets/courseware/v1/2b6e40e93519e1aabeadd896c584f2b3/asset-v1:OCW+6.042J+2T2019+type@asset+block/StrongInduction_1.8_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@98f6c6c5c496416fa9575bd439fb4079" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Unstacking Game Score</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a1ab8945bdd04ea28f33538373db79ec">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a1ab8945bdd04ea28f33538373db79ec" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_a1ab8945bdd04ea28f33538373db79ec" class="problems-wrapper" role="group"
aria-labelledby="a1ab8945bdd04ea28f33538373db79ec-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a1ab8945bdd04ea28f33538373db79ec" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@a1ab8945bdd04ea28f33538373db79ec/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="a1ab8945bdd04ea28f33538373db79ec-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@a1ab8945bdd04ea28f33538373db79ec-problem-progress" tabindex="-1">
Unstacking Game Score
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@a1ab8945bdd04ea28f33538373db79ec-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_a1ab8945bdd04ea28f33538373db79ec_2_1">
<fieldset aria-describedby="status_a1ab8945bdd04ea28f33538373db79ec_2_1">
<legend id="a1ab8945bdd04ea28f33538373db79ec_2_1-legend" class="response-fieldset-legend field-group-hd">Suppose that there is a game that entails unstacking a tower of <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> blocks. A move entails splitting a stack of <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>k</mi>
</math> blocks into two stacks of <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>k</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mi>a</mi>
</math> blocks. Also define the score for a move to be the product of the number of blocks in the created substacks (e.g.<math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>k</mi>
<mo stretchy="false">(</mo>
<mi>a</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</math> ). The overall score for the game is the sum of the scores accumulated over all the moves. Which of the following is true about the overall score?</legend>
<div class="field">
<input type="checkbox" name="input_a1ab8945bdd04ea28f33538373db79ec_2_1[]" id="input_a1ab8945bdd04ea28f33538373db79ec_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="a1ab8945bdd04ea28f33538373db79ec_2_1-choice_0-label" for="input_a1ab8945bdd04ea28f33538373db79ec_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_a1ab8945bdd04ea28f33538373db79ec_2_1"> The score-maximizing strategy is to always split a stack in half.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_a1ab8945bdd04ea28f33538373db79ec_2_1[]" id="input_a1ab8945bdd04ea28f33538373db79ec_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="a1ab8945bdd04ea28f33538373db79ec_2_1-choice_1-label" for="input_a1ab8945bdd04ea28f33538373db79ec_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_a1ab8945bdd04ea28f33538373db79ec_2_1"> The overall score is the same however you unstack the blocks.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_a1ab8945bdd04ea28f33538373db79ec_2_1[]" id="input_a1ab8945bdd04ea28f33538373db79ec_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="a1ab8945bdd04ea28f33538373db79ec_2_1-choice_2-label" for="input_a1ab8945bdd04ea28f33538373db79ec_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_a1ab8945bdd04ea28f33538373db79ec_2_1"> The overall score for a <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math>-stack game is <math xmlns="http://www.w3.org/1998/Math/MathML">
<mfrac>
<mrow>
<mi>n</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
</mrow>
<mn>2</mn>
</mfrac>
</math>.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_a1ab8945bdd04ea28f33538373db79ec_2_1[]" id="input_a1ab8945bdd04ea28f33538373db79ec_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="a1ab8945bdd04ea28f33538373db79ec_2_1-choice_3-label" for="input_a1ab8945bdd04ea28f33538373db79ec_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_a1ab8945bdd04ea28f33538373db79ec_2_1"> The base case is a 2-block stack, which takes one split to unstack.
</label>
</div>
<span id="answer_a1ab8945bdd04ea28f33538373db79ec_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_a1ab8945bdd04ea28f33538373db79ec_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Unstacking Game Score" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_a1ab8945bdd04ea28f33538373db79ec" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_a1ab8945bdd04ea28f33538373db79ec">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="a1ab8945bdd04ea28f33538373db79ec-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a1ab8945bdd04ea28f33538373db79ec-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a1ab8945bdd04ea28f33538373db79ec-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a1ab8945bdd04ea28f33538373db79ec-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@40f5cf1974d9454eb95da0db188c47e9" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | WOP vs Induction (Optional)</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@f99fd738ee5b42418c1bf149c86f2cc9">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@f99fd738ee5b42418c1bf149c86f2cc9" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">WOP vs Induction</h3>
<div
id="video_f99fd738ee5b42418c1bf149c86f2cc9"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:K8ZfzNN1miQ", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@f99fd738ee5b42418c1bf149c86f2cc9/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@f99fd738ee5b42418c1bf149c86f2cc9/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_WOPvsInduction_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@f99fd738ee5b42418c1bf149c86f2cc9/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@f99fd738ee5b42418c1bf149c86f2cc9/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="f99fd738ee5b42418c1bf149c86f2cc9"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_f99fd738ee5b42418c1bf149c86f2cc9">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_f99fd738ee5b42418c1bf149c86f2cc9">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_WOPvsInduction_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@f99fd738ee5b42418c1bf149c86f2cc9/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@f99fd738ee5b42418c1bf149c86f2cc9/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@0c60f4ce3b5044b1b95ebe1274e76992">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@0c60f4ce3b5044b1b95ebe1274e76992" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/1ad458073e17d87e1158b8b84111615c/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS16_WOPvsInductn.pdf" target="[object Object]">Ordinary Induction vs Strong Induction vs WOP (PDF)</a></p>
<p><a href="/assets/courseware/v1/b72058b3e0cae78c7d49051bf7d05b32/asset-v1:OCW+6.042J+2T2019+type@asset+block/WOP_1.8_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@c30805ebe9554e89883abc2faa3bfc41" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Strong vs Ordinary Induction vs WOP (Optional)</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@1b6c0bf7aa4e4ad39b2d78e38bcb200d">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@1b6c0bf7aa4e4ad39b2d78e38bcb200d" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_1b6c0bf7aa4e4ad39b2d78e38bcb200d" class="problems-wrapper" role="group"
aria-labelledby="1b6c0bf7aa4e4ad39b2d78e38bcb200d-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@1b6c0bf7aa4e4ad39b2d78e38bcb200d" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@1b6c0bf7aa4e4ad39b2d78e38bcb200d/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="1b6c0bf7aa4e4ad39b2d78e38bcb200d-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@1b6c0bf7aa4e4ad39b2d78e38bcb200d-problem-progress" tabindex="-1">
Strong vs Ordinary Induction vs WOP
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@1b6c0bf7aa4e4ad39b2d78e38bcb200d-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>1. Which of the following is / are correct about Ordinary Induction and Strong Induction? </p>
<div class="choicegroup capa_inputtype" id="inputtype_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1">
<fieldset aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1">
<div class="field">
<input type="checkbox" name="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1[]" id="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1-choice_0-label" for="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1"> Strong induction and ordinary induction are technically equivalent.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1[]" id="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1-choice_1-label" for="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1"> Ordinary induction can be seen as a special case of strong induction where some of the assumptions are not used.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1[]" id="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1-choice_2-label" for="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1"> A strong induction proof can be turned into ordinary induction by copying the strong induction proof with the assumptions about <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</math> for <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>k</mi>
<mo>&lt;</mo>
<mi>n</mi>
</math> left out.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1[]" id="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1-choice_3-label" for="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1"> How to turn a strong induction proof into an ordinary one? Revise the induction hypothesis to <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>Q</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mo>::=</mo>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>k</mi>
<mo>&#8804;<!-- &#8804; --></mo>
<mi>n</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</math>.
</label>
</div>
<span id="answer_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>2. When should one use Induction vs WOP? </p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1">
<fieldset aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1">
<div class="field">
<input type="radio" name="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1" id="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1-choice_0-label" for="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1"> It is a matter of taste - proofs that work for one can be phrased to work for the other.
</label>
</div>
<div class="field">
<input type="radio" name="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1" id="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1-choice_1-label" for="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1"> Induction should be used whenever there is a clear base case presented.
</label>
</div>
<div class="field">
<input type="radio" name="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1" id="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1-choice_2-label" for="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1"> Induction should be used whenever one wants to prove that something holds for all <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false"/>
<mi>n</mi>
<mo stretchy="false"/>
</math>.
</label>
</div>
<div class="field">
<input type="radio" name="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1" id="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1-choice_3-label" for="input_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1"> WOP should be used whenever one wants to prove that something holds for all <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false"/>
<mi>n</mi>
<mo stretchy="false"/>
</math>.
</label>
</div>
<span id="answer_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_1b6c0bf7aa4e4ad39b2d78e38bcb200d_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Strong vs Ordinary Induction vs WOP" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_1b6c0bf7aa4e4ad39b2d78e38bcb200d" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_1b6c0bf7aa4e4ad39b2d78e38bcb200d">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="1b6c0bf7aa4e4ad39b2d78e38bcb200d-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1b6c0bf7aa4e4ad39b2d78e38bcb200d-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1b6c0bf7aa4e4ad39b2d78e38bcb200d-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1b6c0bf7aa4e4ad39b2d78e38bcb200d-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@8acd825cb4ba46248cdc4a964da107a0" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Induction by n+3</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@bfe013a71dd24e11af0a20ea275d14a0">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@bfe013a71dd24e11af0a20ea275d14a0" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_bfe013a71dd24e11af0a20ea275d14a0" class="problems-wrapper" role="group"
aria-labelledby="bfe013a71dd24e11af0a20ea275d14a0-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@bfe013a71dd24e11af0a20ea275d14a0" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@bfe013a71dd24e11af0a20ea275d14a0/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="bfe013a71dd24e11af0a20ea275d14a0-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@bfe013a71dd24e11af0a20ea275d14a0-problem-progress" tabindex="-1">
Induction by n+3
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@bfe013a71dd24e11af0a20ea275d14a0-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_bfe013a71dd24e11af0a20ea275d14a0_2_1">
<fieldset aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1">
<legend id="bfe013a71dd24e11af0a20ea275d14a0_2_1-legend" class="response-fieldset-legend field-group-hd">Alice wants to prove by induction that predicate <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
</math> holds for certain nonnegative integers. She has proven that for all nonnegative integers <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>=</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mn>3</mn>
<mo>&#8230;<!-- &#8230; --></mo>
</math>
<br/>
<br/>
<div align="center">
<math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mtext>&#160;IMPLIES&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>+</mo>
<mn>3</mn>
<mo stretchy="false">)</mo>
</math>
</div>
<br/>
<br/>
1. Suppose Alice also proves that <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>5</mn>
<mo stretchy="false">)</mo>
</math> holds. Which of the following propositions can she infer? The universe of discourse for <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> is the nonnegative integers.</legend>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_2_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="bfe013a71dd24e11af0a20ea275d14a0_2_1-choice_0-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> holds for all <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>&#8805;<!-- &#8805; --></mo>
<mn>5</mn>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_2_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="bfe013a71dd24e11af0a20ea275d14a0_2_1-choice_1-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>3</mn>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> holds that for all <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>&#8805;<!-- &#8805; --></mo>
<mn>5</mn>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_2_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="bfe013a71dd24e11af0a20ea275d14a0_2_1-choice_2-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> holds for <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>=</mo>
<mn>8</mn>
<mo>,</mo>
<mn>11</mn>
<mo>,</mo>
<mn>14</mn>
<mo>,</mo>
<mo>&#8230;<!-- &#8230; --></mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_2_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="bfe013a71dd24e11af0a20ea275d14a0_2_1-choice_3-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> does not hold for <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>&#8804;<!-- &#8804; --></mo>
<mn>4</mn>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_2_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="bfe013a71dd24e11af0a20ea275d14a0_2_1-choice_4-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>n</mi>
<mo>.</mo>
<mspace width="thickmathspace"/>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>3</mn>
<mi>n</mi>
<mo>+</mo>
<mn>5</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_2_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="bfe013a71dd24e11af0a20ea275d14a0_2_1-choice_5-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>n</mi>
<mo>&gt;</mo>
<mn>2.</mn>
<mspace width="thickmathspace"/>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>3</mn>
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_2_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="bfe013a71dd24e11af0a20ea275d14a0_2_1-choice_6-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
<mtext>&#160;IMPLIES&#160;</mtext>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>n</mi>
<mo>.</mo>
<mspace width="thickmathspace"/>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>3</mn>
<mi>n</mi>
<mo>+</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_2_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="bfe013a71dd24e11af0a20ea275d14a0_2_1-choice_7-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_2_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
<mtext>&#160;IMPLIES&#160;</mtext>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>n</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>3</mn>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<span id="answer_bfe013a71dd24e11af0a20ea275d14a0_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_bfe013a71dd24e11af0a20ea275d14a0_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_bfe013a71dd24e11af0a20ea275d14a0_3_1">
<fieldset aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1">
<legend id="bfe013a71dd24e11af0a20ea275d14a0_3_1-legend" class="response-fieldset-legend field-group-hd">2. Which of the following could Alice prove in order to conclude that <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> holds for all <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>&#8805;<!-- &#8805; --></mo>
<mn>5</mn>
</math>?</legend>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_3_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="bfe013a71dd24e11af0a20ea275d14a0_3_1-choice_0-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_3_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="bfe013a71dd24e11af0a20ea275d14a0_3_1-choice_1-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>5</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_3_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="bfe013a71dd24e11af0a20ea275d14a0_3_1-choice_2-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>5</mn>
<mo stretchy="false">)</mo>
<mtext>&#160;and&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>6</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_3_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="bfe013a71dd24e11af0a20ea275d14a0_3_1-choice_3-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mtext>&#160;and&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_3_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="bfe013a71dd24e11af0a20ea275d14a0_3_1-choice_4-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>5</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>6</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mtext>&#160;and&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>7</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_3_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="bfe013a71dd24e11af0a20ea275d14a0_3_1-choice_5-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>4</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mtext>&#160;and&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>5</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_3_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="bfe013a71dd24e11af0a20ea275d14a0_3_1-choice_6-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>4</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mtext>&#160;and&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>6</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_bfe013a71dd24e11af0a20ea275d14a0_3_1[]" id="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="bfe013a71dd24e11af0a20ea275d14a0_3_1-choice_7-label" for="input_bfe013a71dd24e11af0a20ea275d14a0_3_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_bfe013a71dd24e11af0a20ea275d14a0_3_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>3</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>5</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mtext>&#160;and&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>7</mn>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<span id="answer_bfe013a71dd24e11af0a20ea275d14a0_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_bfe013a71dd24e11af0a20ea275d14a0_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_bfe013a71dd24e11af0a20ea275d14a0_solution_1"/>
</div><div class="solution-span">
<span id="solution_bfe013a71dd24e11af0a20ea275d14a0_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Induction by n+3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_bfe013a71dd24e11af0a20ea275d14a0" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_bfe013a71dd24e11af0a20ea275d14a0">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="bfe013a71dd24e11af0a20ea275d14a0-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="bfe013a71dd24e11af0a20ea275d14a0-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="bfe013a71dd24e11af0a20ea275d14a0-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="bfe013a71dd24e11af0a20ea275d14a0-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@c756f0ab4b7c45a5b941f643acd174ee" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Induction Rules</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@969e7ace335b416a9232918718f33bd3">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@969e7ace335b416a9232918718f33bd3" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Consider the following three fundamental principles for reasoning about nonnegative integers:</p>
<p></p>
<ul>
<li style="text-align: left;">the Induction Principle,</li>
<li style="text-align: left;">the Strong Induction Principle,</li>
<li style="text-align: left;">the Well Ordering Principle.</li>
</ul>
<p></p>
<p>Indicate the principle behind each of the inference rules over natural numbers below:</p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@36207fdaeea0404ba6f84691852ff866">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@36207fdaeea0404ba6f84691852ff866" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_36207fdaeea0404ba6f84691852ff866" class="problems-wrapper" role="group"
aria-labelledby="36207fdaeea0404ba6f84691852ff866-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@36207fdaeea0404ba6f84691852ff866" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@36207fdaeea0404ba6f84691852ff866/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="5"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="36207fdaeea0404ba6f84691852ff866-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@36207fdaeea0404ba6f84691852ff866-problem-progress" tabindex="-1">
Questions
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@36207fdaeea0404ba6f84691852ff866-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_36207fdaeea0404ba6f84691852ff866_2_1" id="label_36207fdaeea0404ba6f84691852ff866_2_1">1. <math xmlns="http://www.w3.org/1998/Math/MathML">
<mstyle displaystyle="true" scriptlevel="0">
<mfrac>
<mrow>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>m</mi>
<mo>.</mo>
<mo stretchy="false">(</mo>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>k</mi>
<mo>&#8804;<!-- &#8804; --></mo>
<mi>m</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">)</mo>
<mtext>&#160;IMPLIES&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>m</mi>
<mo>+</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
</mrow>
<mrow>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>n</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mrow>
</mfrac>
</mstyle>
</math></label>
<p class="question-description" id="description_36207fdaeea0404ba6f84691852ff866_1_1"> This is a formulation of:</p>
<select name="input_36207fdaeea0404ba6f84691852ff866_2_1" id="input_36207fdaeea0404ba6f84691852ff866_2_1" aria-describedby="status_36207fdaeea0404ba6f84691852ff866_2_1 description_36207fdaeea0404ba6f84691852ff866_1_1">
<option value="option_36207fdaeea0404ba6f84691852ff866_2_1_dummy_default">Select an option</option>
<option value="Ordinary Induction"> Ordinary Induction</option>
<option value="Strong Induction"> Strong Induction</option>
<option value="Well Ordering"> Well Ordering</option>
<option value="None of the above"> None of the above</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_36207fdaeea0404ba6f84691852ff866_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_36207fdaeea0404ba6f84691852ff866_2_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_36207fdaeea0404ba6f84691852ff866_3_1" id="label_36207fdaeea0404ba6f84691852ff866_3_1">2. <math xmlns="http://www.w3.org/1998/Math/MathML">
<mstyle displaystyle="true" scriptlevel="0">
<mfrac>
<mrow>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>b</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>k</mi>
<mo>&#8805;<!-- &#8805; --></mo>
<mi>b</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mtext>&#160;IMPLIES&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
</mrow>
<mrow>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>m</mi>
<mo>&#8805;<!-- &#8805; --></mo>
<mi>b</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>m</mi>
<mo stretchy="false">)</mo>
</mrow>
</mfrac>
</mstyle>
</math></label>
<p class="question-description" id="description_36207fdaeea0404ba6f84691852ff866_2_1"> This is a formulation of:</p>
<select name="input_36207fdaeea0404ba6f84691852ff866_3_1" id="input_36207fdaeea0404ba6f84691852ff866_3_1" aria-describedby="status_36207fdaeea0404ba6f84691852ff866_3_1 description_36207fdaeea0404ba6f84691852ff866_2_1">
<option value="option_36207fdaeea0404ba6f84691852ff866_3_1_dummy_default">Select an option</option>
<option value="Ordinary Induction"> Ordinary Induction</option>
<option value="Strong Induction"> Strong Induction</option>
<option value="Well Ordering"> Well Ordering</option>
<option value="None of the above"> None of the above</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_36207fdaeea0404ba6f84691852ff866_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_36207fdaeea0404ba6f84691852ff866_3_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_36207fdaeea0404ba6f84691852ff866_4_1" id="label_36207fdaeea0404ba6f84691852ff866_4_1">3.<math xmlns="http://www.w3.org/1998/Math/MathML">
<mstyle displaystyle="true" scriptlevel="0">
<mfrac>
<mrow>
<mi mathvariant="normal">&#8707;<!-- &#8707; --></mi>
<mi>n</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mrow>
<mrow>
<mi mathvariant="normal">&#8707;<!-- &#8707; --></mi>
<mi>m</mi>
<mo>.</mo>
<mo stretchy="false">(</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>m</mi>
<mo stretchy="false">)</mo>
<mtext>&#160;AND&#160;</mtext>
<mo stretchy="false">(</mo>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>k</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mtext>&#160;IMPLIES&#160;</mtext>
<mi>k</mi>
<mo>&#8805;<!-- &#8805; --></mo>
<mi>m</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">)</mo>
</mrow>
</mfrac>
</mstyle>
</math></label>
<p class="question-description" id="description_36207fdaeea0404ba6f84691852ff866_3_1"> This is a formulation of:</p>
<select name="input_36207fdaeea0404ba6f84691852ff866_4_1" id="input_36207fdaeea0404ba6f84691852ff866_4_1" aria-describedby="status_36207fdaeea0404ba6f84691852ff866_4_1 description_36207fdaeea0404ba6f84691852ff866_3_1">
<option value="option_36207fdaeea0404ba6f84691852ff866_4_1_dummy_default">Select an option</option>
<option value="Ordinary Induction"> Ordinary Induction</option>
<option value="Strong Induction"> Strong Induction</option>
<option value="Well Ordering"> Well Ordering</option>
<option value="None of the above"> None of the above</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_36207fdaeea0404ba6f84691852ff866_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_36207fdaeea0404ba6f84691852ff866_4_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_36207fdaeea0404ba6f84691852ff866_5_1" id="label_36207fdaeea0404ba6f84691852ff866_5_1">4. <math xmlns="http://www.w3.org/1998/Math/MathML">
<mstyle displaystyle="true" scriptlevel="0">
<mfrac>
<mrow>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>k</mi>
<mo>&gt;</mo>
<mn>0.</mn>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mtext>&#160;IMPLIES&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
</mrow>
<mrow>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>n</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mrow>
</mfrac>
</mstyle>
</math></label>
<p class="question-description" id="description_36207fdaeea0404ba6f84691852ff866_4_1"> This is a formulation of:</p>
<select name="input_36207fdaeea0404ba6f84691852ff866_5_1" id="input_36207fdaeea0404ba6f84691852ff866_5_1" aria-describedby="status_36207fdaeea0404ba6f84691852ff866_5_1 description_36207fdaeea0404ba6f84691852ff866_4_1">
<option value="option_36207fdaeea0404ba6f84691852ff866_5_1_dummy_default">Select an option</option>
<option value="Ordinary Induction"> Ordinary Induction</option>
<option value="Strong Induction"> Strong Induction</option>
<option value="Well Ordering"> Well Ordering</option>
<option value="None of the above"> None of the above</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_36207fdaeea0404ba6f84691852ff866_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_36207fdaeea0404ba6f84691852ff866_5_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 5" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_36207fdaeea0404ba6f84691852ff866_6_1" id="label_36207fdaeea0404ba6f84691852ff866_6_1">5.<math xmlns="http://www.w3.org/1998/Math/MathML">
<mstyle displaystyle="true" scriptlevel="0">
<mfrac>
<mrow>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>m</mi>
<mo>.</mo>
<mo stretchy="false">(</mo>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>k</mi>
<mo>&lt;</mo>
<mi>m</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">)</mo>
<mtext>&#160;IMPLIES&#160;</mtext>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>m</mi>
<mo stretchy="false">)</mo>
</mrow>
<mrow>
<mi mathvariant="normal">&#8704;<!-- &#8704; --></mi>
<mi>n</mi>
<mo>.</mo>
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mrow>
</mfrac>
</mstyle>
</math></label>
<p class="question-description" id="description_36207fdaeea0404ba6f84691852ff866_5_1"> This is a formulation of:</p>
<select name="input_36207fdaeea0404ba6f84691852ff866_6_1" id="input_36207fdaeea0404ba6f84691852ff866_6_1" aria-describedby="status_36207fdaeea0404ba6f84691852ff866_6_1 description_36207fdaeea0404ba6f84691852ff866_5_1">
<option value="option_36207fdaeea0404ba6f84691852ff866_6_1_dummy_default">Select an option</option>
<option value="Ordinary Induction"> Ordinary Induction</option>
<option value="Strong Induction"> Strong Induction</option>
<option value="Well Ordering"> Well Ordering</option>
<option value="None of the above"> None of the above</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_36207fdaeea0404ba6f84691852ff866_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_36207fdaeea0404ba6f84691852ff866_6_1"/>
</div></div>
<div class="solution-span">
<span id="solution_36207fdaeea0404ba6f84691852ff866_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Questions" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_36207fdaeea0404ba6f84691852ff866" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_36207fdaeea0404ba6f84691852ff866">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="36207fdaeea0404ba6f84691852ff866-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="36207fdaeea0404ba6f84691852ff866-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="36207fdaeea0404ba6f84691852ff866-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="36207fdaeea0404ba6f84691852ff866-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@ba86fc8e8e084682993e4554e9bc92c2" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Postage by Induction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@72a0cb39db324eb0b4867a5c49895d2e">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@72a0cb39db324eb0b4867a5c49895d2e" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_72a0cb39db324eb0b4867a5c49895d2e" class="problems-wrapper" role="group"
aria-labelledby="72a0cb39db324eb0b4867a5c49895d2e-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@72a0cb39db324eb0b4867a5c49895d2e" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@72a0cb39db324eb0b4867a5c49895d2e/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="72a0cb39db324eb0b4867a5c49895d2e-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@72a0cb39db324eb0b4867a5c49895d2e-problem-progress" tabindex="-1">
Postage by Induction
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@72a0cb39db324eb0b4867a5c49895d2e-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>Choose the best comment about approaches for proving that any amount of postage greater than or equal to 12 cents can be put together using only 4-cent and 5-cent stamps.</p>
<div class="choicegroup capa_inputtype" id="inputtype_72a0cb39db324eb0b4867a5c49895d2e_2_1">
<fieldset aria-describedby="status_72a0cb39db324eb0b4867a5c49895d2e_2_1">
<div class="field">
<input type="radio" name="input_72a0cb39db324eb0b4867a5c49895d2e_2_1" id="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="72a0cb39db324eb0b4867a5c49895d2e_2_1-choice_0-label" for="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_72a0cb39db324eb0b4867a5c49895d2e_2_1"> Induction (either Ordinary or Strong) would be simpler than WOP.
</label>
</div>
<div class="field">
<input type="radio" name="input_72a0cb39db324eb0b4867a5c49895d2e_2_1" id="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="72a0cb39db324eb0b4867a5c49895d2e_2_1-choice_1-label" for="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_72a0cb39db324eb0b4867a5c49895d2e_2_1"> Ordinary Induction would be the easiest to justify.
</label>
</div>
<div class="field">
<input type="radio" name="input_72a0cb39db324eb0b4867a5c49895d2e_2_1" id="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="72a0cb39db324eb0b4867a5c49895d2e_2_1-choice_2-label" for="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_72a0cb39db324eb0b4867a5c49895d2e_2_1"> Induction, Strong Induction, and WOP all work, but Ordinary Induction is simplest in this case.
</label>
</div>
<div class="field">
<input type="radio" name="input_72a0cb39db324eb0b4867a5c49895d2e_2_1" id="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="72a0cb39db324eb0b4867a5c49895d2e_2_1-choice_3-label" for="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_72a0cb39db324eb0b4867a5c49895d2e_2_1"> Induction, Strong Induction, and WOP all work, but Strong Induction and WOP are easier in this case.
</label>
</div>
<div class="field">
<input type="radio" name="input_72a0cb39db324eb0b4867a5c49895d2e_2_1" id="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="72a0cb39db324eb0b4867a5c49895d2e_2_1-choice_4-label" for="input_72a0cb39db324eb0b4867a5c49895d2e_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_72a0cb39db324eb0b4867a5c49895d2e_2_1"> Induction, Strong Induction, and WOP all work, but WOP would be least desirable, since proof by contradiction should be avoided.
</label>
</div>
<span id="answer_72a0cb39db324eb0b4867a5c49895d2e_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_72a0cb39db324eb0b4867a5c49895d2e_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_72a0cb39db324eb0b4867a5c49895d2e_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Postage by Induction" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_72a0cb39db324eb0b4867a5c49895d2e" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_72a0cb39db324eb0b4867a5c49895d2e">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="72a0cb39db324eb0b4867a5c49895d2e-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="72a0cb39db324eb0b4867a5c49895d2e-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="72a0cb39db324eb0b4867a5c49895d2e-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="72a0cb39db324eb0b4867a5c49895d2e-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@6f9d741d159c477cb187d493947da998" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | A Bogus Induction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4dac2cc450a84d4a8c23a81acc983672">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4dac2cc450a84d4a8c23a81acc983672" data-request-token="b765dd4ce12211ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_4dac2cc450a84d4a8c23a81acc983672" class="problems-wrapper" role="group"
aria-labelledby="4dac2cc450a84d4a8c23a81acc983672-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4dac2cc450a84d4a8c23a81acc983672" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@4dac2cc450a84d4a8c23a81acc983672/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="4dac2cc450a84d4a8c23a81acc983672-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@4dac2cc450a84d4a8c23a81acc983672-problem-progress" tabindex="-1">
A Bogus Induction
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@4dac2cc450a84d4a8c23a81acc983672-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_4dac2cc450a84d4a8c23a81acc983672_2_1">
<fieldset aria-describedby="status_4dac2cc450a84d4a8c23a81acc983672_2_1">
<legend id="4dac2cc450a84d4a8c23a81acc983672_2_1-legend" class="response-fieldset-legend field-group-hd">The Fibonacci numbers <math xmlns="http://www.w3.org/1998/Math/MathML">
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo>,</mo>
<mn>1</mn>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mn>5</mn>
<mo>,</mo>
<mn>8</mn>
<mo>,</mo>
<mn>13</mn>
<mo>,</mo>
<mo>&#8230;<!-- &#8230; --></mo>
</math>
<br/>
<br/>
are defined as follows: let <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> be the <math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>t</mi>
<mi>h</mi>
</mrow>
</msup>
</math> Fibonacci number,
<br/>
<br/>
<ul>
<ui> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
<mo>::=</mo>
<mn>0</mn>
</math></ui>
<br/>
<br/>
<ui> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>::=</mo>
<mn>1</mn>
</math></ui>
<br/>
<br/>
<ui><math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mo>::=</mo>
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mspace width="thickmathspace"/>
<mspace width="thickmathspace"/>
<mtext>&#160;for&#160;</mtext>
<mi>n</mi>
<mo>&#8805;<!-- &#8805; --></mo>
<mn>2</mn>
</math></ui>
</ul>
<b>Bogus Claim:</b> Every Fibonacci number is even.
<br/>
<br/>
Which step(s) in the proof contain <em>logical</em> errors?</legend>
<div class="field">
<input type="checkbox" name="input_4dac2cc450a84d4a8c23a81acc983672_2_1[]" id="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="4dac2cc450a84d4a8c23a81acc983672_2_1-choice_0-label" for="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_4dac2cc450a84d4a8c23a81acc983672_2_1"> Proof by strong induction.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4dac2cc450a84d4a8c23a81acc983672_2_1[]" id="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="4dac2cc450a84d4a8c23a81acc983672_2_1-choice_1-label" for="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_4dac2cc450a84d4a8c23a81acc983672_2_1"> Induction hypothesis: <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> is even.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4dac2cc450a84d4a8c23a81acc983672_2_1[]" id="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="4dac2cc450a84d4a8c23a81acc983672_2_1-choice_2-label" for="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_4dac2cc450a84d4a8c23a81acc983672_2_1"> Base case: <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>0</mn>
</math> , which is an even number.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4dac2cc450a84d4a8c23a81acc983672_2_1[]" id="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="4dac2cc450a84d4a8c23a81acc983672_2_1-choice_3-label" for="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_4dac2cc450a84d4a8c23a81acc983672_2_1"> Induction step: suppose <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>&#8805;<!-- &#8805; --></mo>
<mn>2</mn>
</math>, we assume <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</math> is even for all <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>k</mi>
<mo>&lt;</mo>
<mi>n</mi>
</math>.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4dac2cc450a84d4a8c23a81acc983672_2_1[]" id="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="4dac2cc450a84d4a8c23a81acc983672_2_1-choice_4-label" for="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_4dac2cc450a84d4a8c23a81acc983672_2_1"> By assumption, both <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
</math> are even.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4dac2cc450a84d4a8c23a81acc983672_2_1[]" id="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="4dac2cc450a84d4a8c23a81acc983672_2_1-choice_5-label" for="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_4dac2cc450a84d4a8c23a81acc983672_2_1"> Therefore, <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> is even, since <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
</math> and the sum of two even numbers is even.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4dac2cc450a84d4a8c23a81acc983672_2_1[]" id="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="4dac2cc450a84d4a8c23a81acc983672_2_1-choice_6-label" for="input_4dac2cc450a84d4a8c23a81acc983672_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_4dac2cc450a84d4a8c23a81acc983672_2_1"> Conclusion: the strong induction principle implies that <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>F</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</math> is even for all <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>&gt;</mo>
<mn>0.</mn>
<mspace width="thickmathspace"/>
<mspace width="thickmathspace"/>
<mspace width="thickmathspace"/>
<mi>&#9724;<!-- &#9724; --></mi>
</math>
</label>
</div>
<span id="answer_4dac2cc450a84d4a8c23a81acc983672_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_4dac2cc450a84d4a8c23a81acc983672_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_4dac2cc450a84d4a8c23a81acc983672_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="A Bogus Induction" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_4dac2cc450a84d4a8c23a81acc983672" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_4dac2cc450a84d4a8c23a81acc983672">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="4dac2cc450a84d4a8c23a81acc983672-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4dac2cc450a84d4a8c23a81acc983672-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4dac2cc450a84d4a8c23a81acc983672-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4dac2cc450a84d4a8c23a81acc983672-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>