Exercise 6.4.7

Proof. Let $G_n$ be the subgroup of $S_n$ generated by the transpositions $(1,2),(2,3),\cdots ,(n-1,n)$:

For all $i\in \{1,\cdots ,n\}$, there exists $g\in G_n$ such that $g(n)=i$.

Indeed, if $g=(i,i+1)\circ (i+1,i+2)\circ \cdots \circ (n-1,n)=(i,i+1)(i+1,i+2)\cdots (n-1,n)$ (with the convention $g=e$ if $i=n$), then $g\in G_n$ and $g(n)=i$ (as ${\mathcal{}O}_n=[1,n]$, $G_n$ is a transitive subgroup of $S_n$).

Conclusion: for all $i\in \{1,\dots ,n\}$, there exists $g\in G_n$ such that $g(n)=i$.

We show that $G_n=S_n$.

$S_2=\{e,(1,2)\}$ is equal to $G_2=⟨(1,2)⟩$.

By induction, we suppose that $S_{n-1}=G_{n-1}(n\ge 3)$.

The subgroup of $S_n$ of the permutations fixing $n$ is identified with $S_{n-1}$, so

Let $\sigma \in S_n$ and $i=\sigma (n)$. By the above conclusion, there exists $g\in G_n$ such that $g(n)=i$. Then

Thus $\sigma =g\circ g^{\prime }$, where $g\in G_n,g^{\prime }\in G_{n-1}\subset G_n$, therefore $\sigma \in G_n$. So $S_n\subset G_n$, and by definition $G_n\subset S_n$, thus $G_n=S_n$.

Conclusion: for all $n\ge 2$, $S_n=⟨(1,2),(2,3),\dots ,(n-1,n)⟩$

We recall the following lemma :

Lemma. If $g=(a_1,\dots ,a_k)$is a cycle in $S_n$, and $\sigma \in S_n$, then

Indeed,

$\text{∙}$ If $1\le i<k,(\sigma \circ g\circ {\sigma }^{-1})(\sigma (a_i))=\sigma (g(a_i))=\sigma (a_{i+1}))$.

$\text{∙}$ If $i=k,(\sigma \circ g\circ {\sigma }^{-1})(\sigma (a_k))=\sigma (g(a_k))=\sigma (a_1))$.

$\text{∙}$ if $x\notin \{\sigma (a_1),\dots ,\sigma (a_k)\}$, then ${\sigma }^{-1}(x)\notin \{a_1,\cdots ,a_k\}$,

therefore $g({\sigma }^{-1}(x))={\sigma }^{-1}(x),(\sigma \circ g\circ {\sigma }^{-1})(x)=x$. $\square$

Let $\tau =(1,2),\sigma =(1,2,\dots ,n)$.

We apply the Lemma to $\tau$ and ${\sigma }^{k-1},1\le k<n$ :

Thus $⟨\sigma ,\tau ⟩\supset G_n=S_n$.

Conclusion : $S_n$ is generated by the transposition $(1,2)$ and the $n$-cycle $(1,2\dots ,n)$. □