Timeline for Strong induction without a base case
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2016 at 17:46 | comment | added | Andreas Blass | @MaxisJaisi No. A truth (vacuous or otherwise) only implies true statements. Truths do not imply falsehoods. | |
| Oct 25, 2016 at 7:46 | comment | added | Maxis Jaisi | @AndreasBlass, shouldn't n=0 be true, since all k < 0 is vacuous, and a vacuous truth implies the truth for n=0? | |
| Jun 25, 2013 at 3:02 | review | Late answers | |||
| Jun 27, 2013 at 9:44 | |||||
| Jul 8, 2010 at 1:09 | comment | added | Andreas Blass | In broad terms, this is the same story as the horses: An alleged proof by induction on n fails to handle one value of n, and thus gives nonsense for that value and for larger n. The difference is that Himanshu's argument failed to cover the case n=0, while the horse argument fails to cover the case n=2. | |
| Jul 7, 2010 at 21:25 | comment | added | Willie Wong | Somehow Andreas's explanation reminds me of the "proof" that all horses are of the same colour. | |
| Jul 3, 2010 at 17:18 | comment | added | Andreas Blass | Strong induction doesn't require you to prove the base case provided you really prove all the things that strong induction does require you to prove, namely the "strong induction step" for all n, not just (as you did) for n not equal to 0. In some cases, like your example, a complete proof of the strong induction step may involve treating the n=0 case separately, and then it looks like a base case. Nevertheless, it's a part of the strong induction step. | |
| Jul 3, 2010 at 5:04 | comment | added | Himanshu | Right, so basically we need to check the base case, n = 0. I'm feeling that, the assumption that $\forall k < 0 P(k)$ is true leads to these kind of problems and even in the strong induction I should check the base case. That said, I don't understand why strong induction says that you don't need to prove the base case. | |
| Jul 3, 2010 at 4:45 | comment | added | Andreas Blass | To apply the induction hypothesis "for all natural numbers k smaller than n ..." to n-1, you need not only that (as you said) n-1 < n but also that n-1 is a natural number. That fails when n=0, so your argument doesn't cover the case n=0. | |
| Jul 3, 2010 at 4:25 | history | answered | Himanshu | CC BY-SA 2.5 |