The problem is from "Notes on Geometry" by Rees.
Show that any $\sigma \in S_n$ can be writen as a product involving only the $(n-1)$ transpositions $(1,2),(2,3),...,((n-1),n)$.
- Note: In the book, $S_n$ denotes the symmetric group on $n$ letters. But, in this problem, I think it specifically means natural numbers $1,...,n$ because it doesn't make any sense if it is not (as ndhanson3 said in the comment.)
To prove the statement, first, I showed that any $\sigma \in S_n$ can be rewritten as a product of transpositions.
And then, I showed that $\sigma$ is also a product of transpositions $(1 \; \; 2),(2 \; \; 3),...,(n-1 \; \; n)$.
Now, I'm left with the last step, which is to show that any $\sigma$ is a product of exactly $n-1$ transpositions $(1 \; \; 2),(2 \; \; 3),...,(n-1 \; \; n)$.
I thought I could show it with the inductive method as other answers suggested, but all the answers I could find only showed that $\sigma$ is a product of $n-1$ transpositions (but these transpositions might not be $(1 \; \; 2),(2 \; \; 3),...,(n-1 \; \; n)$.)
Anyways, for the inductive method, I showed that it satisfies for $n=2$ case, then I assumed that it also satisfies for $n=k-1$ case. And here's my work for the $n=k$ case.
Let $\sigma = (a_1 \; \; a_2 \;\; ... a_{k-1} \;\;a_k)$ for arbitrary $a_1,...,a_k \in \{1,...,k\}$, but each $a$'s are distinct.
Then, $\exists a_i \in \{a_1,...,a_k\}$ s.t $ a_i =k$.
But, note that we can always place $k$ in the last place of the cycle. Then, we can decompose the $\sigma$ as $k-2$ many of $(1 \; \; 2),(2 \; \; 3),...,(k-2 \; \; k-1)$ and the other transposition $(a_j \;\;a_i)$ where $a_j \neq a_i$.
We can observe that if $|a_j -a_i|=1$, then there are $k-1$ many transpositions as we desired. However, it is not really clear when $|a_j-a_i|\neq 1$.
I know that we can rewrite such $(a_j \;\; a_i)$ as a product of transpositions like $(a_j \;\; a_{j+1})...(a_{i-1} \;\; a_i)...(a_j \;\; a_{j+1})$. For example, $(1 \; \; 3) = (1 \;\; 2)(2 \;\;3)(1 \; \;2)$, but then I think there must be more than $k-1$ transpositions.
Is there anything I'm missing here? What are the alternative ways to prove the statement?