(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Use induction of n to prove that the transpositions [itex]s_i = (i, i+1)[/itex], [itex]1 \leq i \leq n - 1[/itex] generate [itex]S_n[/itex].

2. Relevant equations

Notation: [itex]e[/itex] = Identity permutation.

Any permutation can be written as a disjoint product of transpositions.

3. The attempt at a solution

Proof. We proceed by induction on n. As our base case for [itex]n=2[/itex], we cite that the transposition [itex]s_1 = (12)[/itex] is sufficient to generate [itex]S_n[/itex] since [itex]s_1^2 = e[/itex]. Suppose now that the transpositions [itex]s_i = (i, i+1)[/itex], [itex]1 \leq i \leq n-1[/itex] generate [itex]S_n[/itex].

I'm not really sure where to go next. I know that [itex]S_n[/itex] has [itex]n![/itex] elements and want to use that fact along with the transposition [itex](i+1,i+2)[/itex] to somehow show that [itex]S_{n+1}[/itex] will have [itex](n+1)![/itex] elements but I am not sure if that is sufficient to prove that the [itex]s_i[/itex]'s generate [itex]S_n[/itex].

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Prove the symmetric group is generated by

**Physics Forums | Science Articles, Homework Help, Discussion**