Induct on for . The result is immediate when . For the inductive step,

The middle transposition is a product of an odd number of adjacent transpositions by induction; adjoining two more preserves odd parity.