Proof about symmetric groups and generators

Let $n \ge 2$, $n \in \mathbb N$ and set $\sigma=(1,2,3,...,n)$ and $\tau=(1,2)$. Show that $\mathrm{Sym}(n)=\left<\sigma,\tau\right>$.

Approach: Induction

Proof:

Base case $n=2$

$\sigma=(1,2)$
$\tau=(1,2)$

$Sym(2)=\{Id_2,(1,2)\}$ $(1,2)=\tau$ and $Id_2=\tau\sigma$

so base case holds

Inductive step assume $Sym(k)=<\sigma,\tau>$ where $\sigma=(1,2,3,4,...,k)$ and $\tau=(1,2)$

Show $Sym(k+1)=<\lambda,\tau>$ where $\lambda={1,2,...,k+1}$ and $\tau=<1,2>$

To prove the inductive step, I was thinking we have to use the fact that every $x\in Sym(k+1)$ can be represented as the product of pairwise disjoint cycles. I think that we can express $\lambda$ in terms of $\sigma$

Your previous question was about transpositions generating $S_n$. So we may try an approach where we attempt to generate all transpositions from the given two permutations.

First, conjugate $(12)$ by $(12\cdots n)$ repeatedly to obtain $(23),(34),\cdots,(n-1\,n)$.

This makes sense once you understand this: $\sigma(a_1\,a_2\,\cdots\,a_k)\sigma^{-1}=(\sigma(a_1)\,\sigma(a_2)\,\cdots\,\sigma(a_k))$.

Second, see if you can conjugate $(i\,i+1)$ by $(j\,j+1)$s systematically to get any $(i\,k)$. For example, conjugating $(12)$ by $(23)$ gives $(13)$, then conjugating that by $(34)$ gives $(14)$.

• I am quite lost, so we are trying to generate every transposition from $Sym(n)$? – TheMathNoob Aug 8 '16 at 7:20
• That's the approach I said I'm discussing in my answer, yes. – arctic tern Aug 8 '16 at 7:29
• and you want me to get somehow $(12)^k(12*****n)^l=(23),(34),....,(n-1,n)$ – TheMathNoob Aug 8 '16 at 7:31
• No. Do you know what conjugate means? – arctic tern Aug 8 '16 at 7:32
• I guess it means somehow to use different combinations of the two permutations to get some desired transposition? – TheMathNoob Aug 8 '16 at 7:33