User:IssaRice/Faulty mathematical induction proof example: Difference between revisions
(Created page with "Consider the following "proof": <blockquote style="border: 1px solid black; padding: 10px;"><p>'''Proposition.''' Let <math>b,c</math> be positive integers. Then <math>bc > b...") |
No edit summary |
||
| Line 1: | Line 1: | ||
==Problem statement== | |||
Consider the following "proof": | Consider the following "proof": | ||
| Line 4: | Line 6: | ||
<p>''Proof.'' We fix <math>b > 0</math> and induct on <math>c</math>. For the base case when <math>c=0</math>, the result is vacuously true. Now suppose inductively that we have the result for <math>c</math>. Then for <math>c+1</math> we need <math>b(c+1) > b</math>. But <math>b(c+1) = bc+b > bc</math> since <math>b > 0</math>. Also, <math>bc > b</math> by induction hypothesis. Therefore, <math>bc+b > bc | <p>''Proof.'' We fix <math>b > 0</math> and induct on <math>c</math>. For the base case when <math>c=0</math>, the result is vacuously true. Now suppose inductively that we have the result for <math>c</math>. Then for <math>c+1</math> we need <math>b(c+1) > b</math>. But <math>b(c+1) = bc+b > bc</math> since <math>b > 0</math>. Also, <math>bc > b</math> by induction hypothesis. Therefore, <math>bc+b > bc | ||
> b</math>. This closes the induction.</p></blockquote> | > b</math>. This closes the induction.</p></blockquote> | ||
This proposition is obviously false, since for <math>c = 1 > 0</math> we have <math>bc = b</math>, not <math>bc > b</math>. | |||
==Diagnosis== | |||
Revision as of 20:44, 13 April 2020
Problem statement
Consider the following "proof":
Proposition. Let be positive integers. Then .
Proof. We fix and induct on . For the base case when , the result is vacuously true. Now suppose inductively that we have the result for . Then for we need . But since . Also, by induction hypothesis. Therefore, . This closes the induction.
This proposition is obviously false, since for we have , not .
