Given $X=\{1,2,......n\}$, let us call a permutation $p$ of $X$ an adjacency if it is a transposition of the form $(i,i+1)$ for $i\le n-1$. Prove that $(i,j)$ is a product of an odd number of adjacencies.
I am stuck in this question, I try to use mathematical induction to prove this question. I know when $j=i+1$, it is obviously right. Then, I try to find how to construct a product of adjacencies which is identical to $(i,i+2)$, but I still have no idea how to construct it. I plan to use mathematical induction to prove it, but I am still not sure how to use it to prove it. Can someone help me solve this question, or can someone give me some hints? Thank you.
Here's the full proof by induction:
We induct on the value of $|j-i|$. Clearly the property holds for $|j-i|$ = 1 because $(i,i \pm 1)$ is the product of one adjacency.
Now, assume it holds for $j-i \leq n$. Consider $(i,i+n+1)$. This equals $(i+n,i)(i+n,i+n+1)(i,i+n)$. By the inductive hypothesis, both $(i+n,i)$ and $(i,i+n)$ are expressible as the product of an odd number of adjacencies. An odd number plus one plus another odd number is odd, so $(i,i+n+1)$ can be expressed as the product of an odd number of adjacencies. Flipping the signs shows that $(i,i-n-i)$ is similarly expressible. This complete the induction.