Prove by induction that n! > 2" for all natural numbers n >What is wrong with the following proof that all horses have the same color? Let P(a) be the proposition that all the horses in a set of n horses are the same color. Base case: Clearly, P(1) is true. Now assume that P() is true. That is, assume that all the horses in any set of n horses are the same color. Consider any n + 1 horses; number these as horses 1, 2, 3. .... n, n + 1. Now the first n of these horses all must have the same color, and the last n of these must also have the same color. Since the set of the first n horses and the set of the last n horses overlap, all n + 1 must be the same color. This shows that P(a + 1) is true and finishes the proof by induction