Timeline for Strong induction without a base case
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2011 at 4:01 | comment | added | KConrad | Marc: An edit has been made. Thanks for the comment. | |
| Nov 17, 2011 at 4:01 | history | edited | KConrad | CC BY-SA 3.0 |
deleted 11 characters in body
|
| Nov 16, 2011 at 14:56 | comment | added | Marc van Leeuwen | Not only is it not an example, it is not a correct proof. The difference $d(X)$ has not been shown to have nonzero degree, so the induction hypothesis does not apply. If you replace "of nonzero degree" by "nonzero" in the statement, then the argument becomes correct. The smallest case $n=0$ then constructs to a nonzero polynomial of negative degree which ...(vacuous); this is a contradiction in itself. Since no appeal is made to the induction hypothesis for $n=0$, one might say the case is handled differently though. In any case it falls under the "minimal counterexample cannot exist" label. | |
| Jul 3, 2010 at 14:45 | comment | added | Chad Groft | I don't think this is an example. Remember that the zero polynomial has negative degree and every number as a root; so one must argue separately that zero-degree polynomials have no roots. The whole point was to not argue the base case separately. | |
| Jan 18, 2010 at 6:07 | comment | added | Bjorn Poonen | Good example! One comment: The claim is stronger, and the inductive step clearer, if in the claim you change "polynomial of nonzero degree" to "nonzero polynomial". | |
| Jan 17, 2010 at 10:38 | history | edited | KConrad | CC BY-SA 2.5 |
added 2 characters in body; added 2 characters in body
|
| Jan 17, 2010 at 4:10 | comment | added | KConrad | Oh, duh. I was reading "degree than less than n" at the end of the proof as "degree n-1". | |
| Jan 17, 2010 at 4:07 | history | edited | KConrad | CC BY-SA 2.5 |
added 260 characters in body; edited body
|
| Jan 17, 2010 at 2:32 | comment | added | François G. Dorais | It's not the immediately preceding case: $d(X)$ has degree less than $n$, not necessarily $n-1$. (The $n+1$ is misleading, it's just the smallest integer bigger than $n$.) | |
| Jan 17, 2010 at 2:29 | comment | added | KConrad | Really? Although one could run through the argument as a strong induction type statement, it only involves two adjacent cases. I tend to think of true strong inductive arguments as those (like factorization into primes) where you prove one case by appealing to some earlier case, but it in practice is not going to be the immediately preceding case. | |
| Jan 17, 2010 at 2:10 | comment | added | François G. Dorais | You're ok, this does use strong induction. | |
| Jan 17, 2010 at 1:53 | history | answered | KConrad | CC BY-SA 2.5 |