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

$$\tau_m,\tau_{m+1},\dots,\tau_{n-1}.$$

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

$$\rho=\tau_{n-1}\circ\cdots\circ\tau_m\circ\sigma$$

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

$$\rho=\tau_{r_1}\circ\cdots\circ\tau_{r_N}$$

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

$$\sigma=\tau_m\circ\tau_{m+1}\circ\cdots\circ\tau_{n-1}\circ\tau_{r_1}\circ\cdots\circ\tau_{r_N}.$$

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.