show/hide this revision's text 4 Improved presentation. Moved example statement to top line.

Many

My example is the classical proof that sqrt(2) is irrational.

More generally, many proofs that proceed by showing that there are no minimal counterexamples exemplify your phenomenon. (This The method is, of course, equivalent to no-minimal-counterexamples is exactly the same as strong inductionand to the well-order principle.) Often, with but where one proves the no-minimal-counterexample required implication by contradiction. In many applications of this method, it is often clear that the smallest numbers are not counterexamples, and this would not ordinarily regarded as a separate base "case".

The

In the classical proof that sqrt(2) is irrationalis essentially like this. Suppose , for example, we suppose sqrt(2) = p/q, where p is minimal. Now, square both sides and proceed with the usual argument, to arrive at a smaller counterexample. Contradiction! This amounts to a proof by strong induction that no rational number squares to 2, and there seems to be no separate base case here.

Many people

People often carry out the classical argument by assuming p/q is in lowest terms, but the argument I just described does not need this extra complication. Also, in any case, the proof that every rational number can indeed be put into lowest terms is itself another instance of the phenomenon. Namely, if p/q is a counterexample with p minimal, then if you're not already done, divide by any common factor and apply induction. Does the There seems to be no separate base case when here where it is already in lowest termsconstitute a separate base "case"? To my mind, no, but perhaps you object to thissince we were considering a minimal counterexample. Perhaps someone else objects that there is no induction here at all, since one can just divide by the gcd(p,q). But the usual proof that any two numbers have a gcd is, of course, also inductive. The standard proof using : considering the least linear combination xq+yp amounts to strong inductionagain, again with no separate base case.
show/hide this revision's text 3 deleted 14 characters in body

Perhaps many of the

Many proofs that proceed by proving showing that there can be are no minimal counterexample are essentially instances of counterexamples exemplify your phenomenon. (The This method of no-minimal-counterexamples is, of course, fundamentally equivalent to strong induction , and to the well-order principle.) But in many uses of Often, with the no-minimal-counterexample method, it is often completely clear that the smallest numbers are not counterexamplesto whatever is being proved, and these this would not ordinarily be considered regarded as a separate base case.

For example, the "case".

The classical proof that sqrt(2) is irrational is essentially like this. In the first step, one assumes that Suppose sqrt(2) = p/q, where p is minimal. Now, square both sides and proceed with the usual argument, to arrive at a smaller counterexample, ruled out . This amounts to a proof by strong induction that no rational number squares to 2, and there seems to be no separate base case.

Many people carry out the classical argument by assuming p/q is in lowest terms, but the argument I just described does not need this extra complication. NeverthelessAlso, the proof that every rational number can indeed be put into lowest terms is itself another instance of the phenomnonphenomenon. Namely, if p/q is a counterexample with p minimal, then if you're not already done, divide by any common factor and apply induction. Does the case when it is already in lowest terms constitute a separate base "case"? To my mind, no, but perhaps you object to this.

(Perhaps someone else objects that there is no induction here at all, since one can just divide by the gcd(p,q). But the usual proof that any two numbers have a gcd is, of course, also inductive. The standard proof using the least linear combination xq+yp amounts to strong induction.)induction again, with no separate base case.
show/hide this revision's text 2 added 150 characters in body; added 27 characters in body

Perhaps many of the proofs that proceed by proving that there can be no minimal counterexample are essentially instances of your phenomenon. (The method of no-minimal-counterexamples is, of course, fundamentally equivalent to strong induction, and the well-order principle.) But in many uses of no-minimal-counterexample, it is often completely clear that the smallest numbers are not counterexamples to whatever is being proved, and these would not ordinarily be considered a separate base case.

For example, the classical proof that sqrt(2) is irrational is essentially like this. In the first step, one assumes that the putative fraction is in lowest termssqrt(2) = p/q, which where p is to sayminimal. Now, that it is square both sides and proceed with the usual argument, to arrive at a minimal smaller counterexample, ruled out by strong induction.

The inductive aspect of this proof

Many people carry out the classical argument by assuming p/q is contained in lowest terms, but the statement: argument I just described does not need this. Nevertheless, the proof that every rational number can be put into lowest terms is itself another instance of the phenomnon. To prove thisNamely, one may consider an example if p/q where p is a counterexample with p minimal. If it is , then if you're not in lowest terms already done, then divide out by any common divisor factor and apply strong induction. Does the case when it is already in lowest terms constitute a separate base "case"? To my mind, no, but perhaps you object to this.

(Perhaps someone else objects that there is no induction here at all, since one can just divide by the gcd(p,q). But the usual proof that any two numbers have a gcd is, of course, also inductive. The standard proof using the least linear combination xq+yp amounts to strong induction.)
show/hide this revision's text 1 [made Community Wiki]