Prove factoring an r-cycle into transpositions

Question

Prove that $(x_1,x_2,x_3,...,x_r) = (x_1,x_2)\circ(x_2,x_3)\circ(x_3,x_4)\circ...\circ(x_{r-2},x_{r-1})\circ(x_{r-1},x_r)$.

I know that any cycle in $S_n$ can be written as a product of transpositions, namely $(x_1,x_2,x_3,...,x_r) = (x_1,x_r)\circ(x_1,x_{r-1})\circ ...\circ (x_1,x_2)$.

Answer 1

HINT: Prove it by induction on $r$. The key step is to show that

$$(x_1,\ldots,x_{r-1})\circ(x_{r-1},x_r)=(x_1,\ldots,x_r)\;,$$

which is pretty straightforward.

Answer 2

If you compose "right-to-left" this is pretty easy to see:

$x_1$ is unmoved by all transpositions except the left-most, so that the net result is $x_1 \mapsto x_2$.

Similarly, $x_2$ is unmoved by all but the next-to-left-most, where it it gets sent to $x_3$, which is unmoved by the left-most transposition $(x_1\ x_2)$, so that the net result is $x_2 \mapsto x_3$.

Indeed, if $j < r$, then the first transposition (to the left) to affect it is $(x_j\ x_{j+1})$, which sends $x_j \mapsto x_{j+1}$, and all the others to the left no longer affect $x_{j+1}$. This gives a net effect of $x_j \mapsto x_{j+1}$ for all $1 \leq j < r$.

So the only time something nifty happens is with $x_r$, which gets passed straight-away to $x_{r-1}$, and the next transposition to the left sends $x_{r-1}$ to $x_{r-2}$, and the one after that sends $x_{r-2}$ to $x_{r-3}$, and eventually we wind up with $x_3$ which gets sent by $(x_2\ x_3)$ to $x_2$, and finally $x_2$ gets sent by $(x_1\ x_2)$ to $x_1$, giving a "net effect" of sending $x_r \mapsto x_1$.

Brian Scott's suggestion is a bit "cleaner" (induction proofs avoid the vague "eventually" 's and "continuing in this way.." type of hand-waving), but this is what's going on "under the hood".