Use induction on n to show that $\left | G_{n} \right |\leq n!$ for $n\geq 2$. So $G_{n}$ is the group with presentation
 $\left<s_{1},...,s_{n-1}\mid s_{i}^{2}=1, s_{i}s_{j}=s_{j}s_{i} \text{ if } \left | i-j \right |\geq 2, s_{i}s_{j}s_{i}=s_{j}s_{i}s_{j} \text{ if } \left | i-j \right |=1\right>$.
Use induction on n to show that $\left | G_{n} \right |\leq n!$ for $n\geq 2$. Hence conclude that our epimorphism $\theta :G_{n}\rightarrow S_{n}$ is an isomorphism, and so the symmetric group $S_{n}$ has the same presentation as $G_{n}$.
What is a good way to prove this problem? Thanks.
 A: For convenience, I'm going to shift indices a bit. That is, suppose we have shown that $|G_n|\leq n!$ and we will prove it for $G_{n+1}$ (the fact that $|G_2|= 2$ is obvious).
Now, look at the cosets of $G_{n}=\langle s_1,\ldots,s_{n-1}\rangle\leq G_{n+1}$. The proof will follow once we show that the following is a complete list of cosets:
$$\{G_n,\; s_nG_n,\; (s_{n-1}s_n)G_n,\;\ldots, (s_1s_2\cdots s_{n-1}s_n)G_n\}.$$
To prove this, we note that $G_{n+1}$ acts transitively on $G_{n+1}/G_n$. Therefore, if the set above is closed under the action of the generators, it must be everything. So, for $j\leq i$, we compute
$$s_j(s_is_{i+1}\cdots s_n)G_n=\begin{cases}(s_is_{i+1}\cdots s_n)G_n&\mbox{if }j<i-1;\\(s_{i-1}s_is_{i+1}\cdots s_n)G_n&\mbox{if }j=i-1;\\
(s_{i+1}\cdots s_n)G_n&\mbox{if }j=i.
\end{cases}$$ 
For $j>i$, we have
\begin{align*}
s_j(s_is_{i+1}\cdots s_n)G_n&=s_i\cdots (s_js_{j-1}s_j)s_{j+1}\cdots s_n\\
&=s_i\cdots (s_{j-1}s_js_{j-1})s_{j+1}\cdots s_nG_n\\
&=(s_i\cdots s_{j-1}s_j)s_{j-1}(s_{j+1}\cdots s_n)G_n\\
&=(s_i\cdots s_{j-1})(s_js_{j+1}\cdots s_n)s_{j-1}G_n\\
&=s_i\cdots s_{j-1}s_js_{j+1}\cdots s_nG_n.
\end{align*}
Hence, $|G_{n+1}|=(n+1)|G_n|\leq (n+1)n!=(n+1)!$.
A: First show by induction
Lemma. Every element $g$ of $G_n$ can be written with at most one occurance of $s_{n-1}$, i.e., either $g\in G_{n-1}$ or $g=\alpha s_{n-1}\beta$ with $\alpha,\beta\in G_{n-1}$.
Proof. This is clear for $G_2=\langle \,s_1\mid s_1^2=1\,\rangle=\{\epsilon,s_1\}$.
Let $n\ge 2$ and $g\in G_{n+1}$. Assume the minimal number of occurrences of $s_{n}$ in  a word representing $g$ is $k>1$. Then $g=\alpha_1 s_{n}\alpha_2 s_n\beta$ where the $\alpha_1,\alpha_2\in G_{n}$ and $s_{n}$ occurs $k-2$ times in $\beta$. By induction hypothesis, either $\alpha_2\in G_{n-2}$ or $\alpha_2=\gamma_1s_{n-1}\gamma_2$ with $\gamma_1,\gamma_2\in G_{n-2}$.
In the first case, $$g= \alpha_1 s_{n}\alpha_2 s_n\beta=\alpha_1 s_{n}s_n\alpha_2 \beta=\alpha_1 \alpha_2 \beta$$
uses only $k-2$ occurrences of $s_n$, contradiction.
In the second case,
$$g= \alpha_1 s_{n}\alpha_2 s_n\beta=\alpha_1 s_{n}\gamma_1s_{n-1}\gamma_2 s_n\beta=\alpha_1 \gamma_1s_{n}s_{n-1}s_n\gamma_2 \beta=\alpha_1 \gamma_1s_{n-1}s_{n}s_{n-1}\gamma_2 \beta$$
uses only $k-1$ occurrences of $s_n$, contradiction again. $\square$
Corollary. Every element $g\in G_n$ can be written as 
$g=s_ms_{m+1}\cdots s_{n-2}s_{n-1}\alpha $ with $1\le m\le n$ and $\alpha\in G_{n-1}$.
Proof. Again this is clear for $n=2$.
Let $n>2$ and $g\in G_n$.
If $g\in G_{n-1}$ we can let $m=n$, i.e., $s_m\cdots s_{n-1}$ is the empty product and are done. Otherwise we have $g=\alpha s_{n-1}\beta$ with $\alpha,\beta\in G_{n-1}$ by the lemma. By induction hypothesis, $\alpha=s_m\cdots s_{n-2}\gamma$ with $1\le m\le n-1$ and $\gamma\in G_{n-2}$. Then 
$$g=\alpha s_{n-1}\beta=s_m\cdots s_{n-2}\gamma s_{n-1}\beta=s_m\cdots s_{n-2}s_{n-1}\gamma \beta$$
and we are done. $\square$
Corollary. $|G_n|\le n!$
Proof. In the preceding corollary, there are $n$ choices for $m$ and $|G_{n-1}|$ choices for $\alpha$. Hence we have the recursion $|G_n|\le n\cdot |G_{n-1}|$. Then the claim follows from $|G_2|=2$. $\square$
