Thursday, May 1, 2008

lai lai lai chewrens, join the following contest and stand a chance to win a $35 Olympus TRIPOD!!!!!

Spot the error in the following proof:

Claim: All horses are of the same colour

Proof by Mathematical Induction:
Let P(n) be the statement "n horses are of the same colour" for positive integers n

When n = 1, there is only 1 horse and one horse is of the same colour as itself.
Therefore, P(1) is true.

Assume that P(k) is true i.e. "k horses are of the same colour"

To prove: P(k+1) is also true i.e. "(k+1) horses are of the same colour"

When n = k+1,
There are (k+1) horses. Remove 1 horse e.g. horse A. Then we have k horses. From assumption, the k horses have the same colour say Colour 1. Replace horse B (of colour 1) in this remaining set with horse A so the number of horses is still k. From assumption, the k horses have the same colour 1. Now put back horse B and we have (k+1) horses of the same colour 1!
Thus, P(k) is true => P(k+1) is also true!
Since P(1) is true and P(k) is true => P(k+1) is also true, by Mathematical Induction, P(n) is true for all positive integers n.

=)