Homework Help: computer sciece(Computation Theory)

Posted by Alex on Monday, September 26, 2011 at 3:22am.

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.

computer sciece(Computation Theory) - MathMate, Monday, September 26, 2011 at 6:55am
"...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.

Answer this Question

Related Questions

computer sciece - 1.which directory does Vim to load color scheme? 2.Set a key ...
computer sciece - I have a question, how do we find a Voltage, Current, Power if...
Biology 100 - Read Ch. 9, section 9.1, How Did Life Originate? Reasearch a ...
Biology 100 - Read Ch. 9, section 9.1, How Did Life Originate? Reasearch a ...
Physics - Do atoms have colors? What colors are they? Are they all the same ...
Computer Information Systems - Explain what method of output would be best for ...
maths - A & B together have 132 horses. If 0.25 of the no. of A 's ...
Art - If you wish to balance complementary colors so that they'll appear ...
Biology 100 - Choose one theory spontaneous generation theory or cell theory. ...
Statistics - You are responsible for quickly fixing your company¡¯s ...

For Further Reading

First Name:
School Subject:
Answer: