The following is an incorrect proof of For every natural number n 1, in every group of n cars, all the cars are from the same state Proof by induction: Base case: In a group of 1 car, every car (i.e., that one car) is from the same state Induction step: Let n be an arbitrary natural number and suppose that in every group of n cars, all the cars are from the same state Consider a group of n+1 cars. By the induction hypothesis, cars 1 through n are from the same state and cars 2 through n+1 are from the same state Thus cars 1 through n+1 are from the same state This induction proof is obviously incorrect. What's wrong with it?