Difference between revisions of "Fallacious proof/all horses are the same color"
Mathnerd314 (talk | contribs) |
(header) |
||
(4 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | Our base case is not the appropriate base case: if one could show that every pair of horses has the same color (the result for <math>n = 2</math>), the fact that all horses have the same color would follow. Unfortunately, the case <math>n = 2</math> does not follow from the case <math>n = 1</math>. The first horse is the same color as itself, and so is the second horse, but there is no overlap. | + | == All horses are the same color== |
+ | |||
+ | We shall prove that all horses are the same color by induction on the number of horses. | ||
+ | |||
+ | First we shall show our base case, that all horses in a group of 1 horse have the same color, to be true. Of course, there's only 1 horse in the group so certainly our base case holds. | ||
+ | |||
+ | Now assume that all the horses in any group of <math>k</math> horses are the same color. This is our inductive assumption. | ||
+ | |||
+ | Using our inductive assumption, we will now show that all horses in a group of <math>k+1</math> horses have the same color. Number the horses 1 through <math>k+1</math>. Horses 1 through <math>k</math> must be the same color as must horses 2 through <math>k+1</math>. It follows that all of the horses are the same color. | ||
+ | |||
+ | ===Explanation=== | ||
+ | |||
+ | Our base case is not the appropriate base case: if one could show that every pair of horses has the same color (the result for <math>n = 2</math>), the fact that all horses have the same color would follow. Unfortunately, the case <math>n = 2</math> does not follow from the case <math>n = 1</math>. The first horse is the same color as itself, and so is the second horse, but there is no overlap and so we cannot deduce that the two horses are the same color. | ||
+ | |||
+ | [[Fallacious proof | Back to main article]] |
Latest revision as of 20:22, 2 November 2007
All horses are the same color
We shall prove that all horses are the same color by induction on the number of horses.
First we shall show our base case, that all horses in a group of 1 horse have the same color, to be true. Of course, there's only 1 horse in the group so certainly our base case holds.
Now assume that all the horses in any group of horses are the same color. This is our inductive assumption.
Using our inductive assumption, we will now show that all horses in a group of horses have the same color. Number the horses 1 through
. Horses 1 through
must be the same color as must horses 2 through
. It follows that all of the horses are the same color.
Explanation
Our base case is not the appropriate base case: if one could show that every pair of horses has the same color (the result for ), the fact that all horses have the same color would follow. Unfortunately, the case
does not follow from the case
. The first horse is the same color as itself, and so is the second horse, but there is no overlap and so we cannot deduce that the two horses are the same color.