Show that $(1,2),(2,3),...(n-1,n)$ generate $S_n$

Question

Can anyone help me show this? I read this in my classnotes but no proof was given. Thanks.

Answer 1

Note that any permutation can be written as a product of transpositions. So if we can show that any transposition $(i,j)$, $1\le i,j\le n$, can be generated by the given set then we are done. Assume w.l.o.g. that $i<j-1$. Then the product $(i,i+1)(i+1,i+2)\cdots(j-1,j)$ will take $i\mapsto j$ and for every $k$, such that $i<k\le j$, $k\mapsto k-1$. We then apply the product $(j-2,j-1)(j-3,j-2)\cdots(i,i+1)$.

Answer 2

Induction on $n$: for the induction step you need that the usual copy of $S_n$ inside $S_{n+1}$ and $(n\,\, n+1)$ generate $S_{n+1}$. But they generate a transitive subgroup $G$, whose point stabiliser has order $\ge n!$, so $G$ has order at least $(n+1)n!=(n+1)!$.