Editing Mathematical induction (section)

== Example of error in the induction step ==
{{main|All horses are the same color}}
The induction step must be proved for all values of {{mvar|n}}. To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by mathematical induction that [[All horses are the same color|all horses are of the same color]]:<ref>{{cite journal|title=On the nature of mathematical proof|first=Joel E.|last=Cohen | year=1961 | journal=Opus}}. Reprinted in ''A Random Walk in Science'' (R. L. Weber, ed.), Crane, Russak & Co., 1973.</ref>

''Base case:'' in a set of only ''one'' horse, there is only one color.

''Induction step:'' assume as induction hypothesis that within any set of <math>n</math> horses, there is only one color. Now look at any set of <math>n+1</math> horses. Number them: <math>1, 2, 3, \dotsc, n, n+1</math>. Consider the sets <math display="inline">\left\{1, 2, 3, \dotsc, n\right\}</math> and <math display="inline">\left\{2, 3, 4, \dotsc, n+1\right\}</math>. Each is a set of only <math>n</math> horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all <math>n+1</math> horses.

The base case <math>n=1</math> is trivial, and the induction step is correct in all cases <math>n > 1</math>. However, the argument used in the induction step is incorrect for <math>n+1=2</math>, because the statement that "the two sets overlap" is false for <math display="inline">\left\{1\right\}</math> and <math display="inline">\left\{2\right\}</math>.