- #1

Samuelb88

- 162

- 0

## Homework Statement

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].

## Homework Equations

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

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

## 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].