A Strange Case Of Induction

We shall prove by mathematical induction that all cars are of the same make.

First take an arbitrary set consisting of a single car. Trivially, every car in this set is of the same make. So the base case holds.

Now assume that for any set of n cars, where n is some natural number, every car in that set is of the same make. This is the induction hypothesis.

Now take an arbitrary set of n+1 cars. Order them in some arbitrary way. Consider the first n cars in this ordering. This is a set of n cars, so by the induction hypothesis every one of these cars is of the same make. Call the make X. Now consider all the cars from the 2^nd to the (n+1)^th. This is a set of n cars, so by the induction hypothesis each of these cars is of the same make. But every car from the 2^nd to the n^th (a set of n-1 cars) is of make X, and the (n+1)^th car is of the same make as all of those, so clearly the (n+1)^th car is of make X too. In short, every one of our n+1 cars is of make X, and therefore every one of them is of the same make. This completes the induction step.

Since we have shown that the base case holds, and since we have shown that if the statement is true for an arbitrary natural number n then it is true for n+1, we have proved by induction that all cars are of the same make.

Obviously, since not all cars are of the same make, there is a mistake in this proof. A-level students who have learnt the principle of mathematical induction should, by being very careful, be able to spot it.