computer sciece(Computation Theory)
posted by Alex .
Find the error in the following proof that all horses are the same color.
CLAIM: In any set of h horses, all horses are the same color.
PROOF: By induction on h.
Basis: For h = 1. In any set containing just one horse, all horses clearly are the same color.
Induction step: For k 1 assume that the claim is true for h = k and prove that it is true for h = k + 1 . Take any set H of k + 1 horses. We show that all the horses in the set are the same color. Remove one horse from this set to obtain the set H1 with just k horses. By the
induction hypothesis, all the horses in H1 are the same color. Now replace the removed horse and remove a dierent one to obtain the set H2. By the same argument, all the horses in H2 are the same color. Therefore all the horses in H must be the same color, and the proof is complete.

"...prove that it is true for h = k + 1 . Take any set H of k + 1 horses. We show that all the horses in the set are the same color. Remove one horse from this set to obtain the set H1 with just k horses...."
The induction process requires to prove that given the proposition is true for k, then k+1 is true.
The above prove is proving that given k+1 is true, then k is true. So k decreases, and does not help to prove that k+2 ... is true.
Respond to this Question
Similar Questions

math please help
One day, a person went to horse racing area, Instead of counting the number of human and horses, he instead counted 74 heads and 196 legs. Yet he knew the number of humans and horses there. How did he do it, and how many humans and … 
maths
A & B together have 132 horses. If 0.25 of the no. of A 's horses = 0.14285714285714.... of no. of B 's horses, how many horses each has? 
ps 361
there are 16 horses. 8 chickens are white. 7 horses run away. how many horses are left? 
Math
joe has a farm with 99 animal, four times as many cows as horses, twice as many horses as pigs. how many cows, horses and pigs are there? 
Math
On joes farm there are 99 animals. There are four times as many cows as horses on the farm. There are twice as many horses as lives. How many horses, cows, and pigs are there? 
mason
seven horses are entered in a race. If two horses are tied for first place, and there are no ties among the other five horses, in how many ways can the seven horses cross the finish line? 
math
horses are entered in a race. If two horses are tied for first place, and there are no ties among the other five horses, in how many ways can the seven horses cross the finish line? 
math
seven horses are entered in a race. If two horses are tied for first place, and there are no ties among the other five horses, in how many ways can the seven horses cross the finish line? 
satistical mobeling
there are 12 horses in a horse show competition. the top three winning horses receive money. how many possible money winning orders are there for a competition with 12 horses ? 
math
john has horses and chickens he has 3 less chickens than horses, if you count the total number of legs for chickens and horses you will get 24 how many chickens does john have?