Proof of Every Permutation is a Product of Adjacent Transpositions

We argue by induction on $n$. If $n=1$, then $S_1$ contains only the identity permutation, and the conclusion holds with $N=0$.

Assume the statement proved for $n-1$, and let $\sigma\in S_n$. Let $m=\sigma(n)$. If $m<n$, compose $\sigma$ on the left with the adjacent transpositions

The effect is to move the value $m$ step by step to the last position. Thus the permutation

satisfies $\rho(n)=n$.

Now regard $\rho$ as a permutation of $\{1,\dots,n-1\}$. By the induction hypothesis, there exist indices $r_1,\dots,r_N\in\{1,\dots,n-2\}$ such that

on $\{1,\dots,n-1\}$, hence also as permutations in $S_n$. Therefore

This expresses $\sigma$ as a product of adjacent transpositions. The same formula also covers the case $m=n$, where the initial string of adjacent transpositions is empty. This completes the induction.