We can get a permutation p from the trivial permutation (1,2,...,n) by a sequence of, say, k, transpositions. Prove that each transposition changes the number of inversions in the permutation by an odd number. Deduce that if the number k is even then the number of inversions in p is even and if k is odd then the number of inversions in p is odd. This implies the theorem.