[proofplan]
We first verify the displayed relations by direct multiplication. For generation, we let $H := \langle S,T\rangle$ and prove that the left action of $H$ on primitive integer column vectors can reduce every first column of a matrix in $SL_2(\mathbb{Z})$ to $(\pm 1,0)^\top$. Once the first column is reduced, the determinant condition forces the reduced matrix to be either a power of $T$ or $-1$ times a power of $T$, both of which lie in $H$. This shows the original matrix lies in $H$, and the statement for $PSL_2(\mathbb{Z})$ follows by passing to the quotient.
[/proofplan]
[step:Verify the two matrix relations by multiplication]
We compute
\begin{align*}
S^2
&=
\begin{pmatrix}
0 & -1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
0 & -1 \\
1 & 0
\end{pmatrix}
=
\begin{pmatrix}
-1 & 0 \\
0 & -1
\end{pmatrix}
= -I.
\end{align*}
Next,
\begin{align*}
ST
&=
\begin{pmatrix}
0 & -1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix}
=
\begin{pmatrix}
0 & -1 \\
1 & 1
\end{pmatrix},
\\
(ST)^2
&=
\begin{pmatrix}
0 & -1 \\
1 & 1
\end{pmatrix}
\begin{pmatrix}
0 & -1 \\
1 & 1
\end{pmatrix}
=
\begin{pmatrix}
-1 & -1 \\
1 & 0
\end{pmatrix},
\\
(ST)^3
&=
\begin{pmatrix}
-1 & -1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
0 & -1 \\
1 & 1
\end{pmatrix}
=
\begin{pmatrix}
-1 & 0 \\
0 & -1
\end{pmatrix}
= -I.
\end{align*}
Thus $S^2 = (ST)^3 = -I$.
[/step]
[step:Reduce every primitive integer column vector using $S$ and powers of $T$]
Let $H := \langle S,T\rangle$ be the subgroup of $SL_2(\mathbb{Z})$ generated by $S$ and $T$. Since $T \in H$, every integer power $T^q$ with $q \in \mathbb{Z}$ belongs to $H$.
[claim:Primitive column reduction]
For every pair $(a,c) \in \mathbb{Z}^2$ with $\gcd(a,c)=1$, there exist $w \in H$ and $\varepsilon \in \{1,-1\}$ such that
\begin{align*}
w
\begin{pmatrix}
a \\
c
\end{pmatrix}
=
\begin{pmatrix}
\varepsilon \\
0
\end{pmatrix}.
\end{align*}
[/claim]
[proof]
For $q \in \mathbb{Z}$, multiplication by $T^q$ and by $S$ gives
\begin{align*}
T^q
\begin{pmatrix}
a \\
c
\end{pmatrix}
&=
\begin{pmatrix}
1 & q \\
0 & 1
\end{pmatrix}
\begin{pmatrix}
a \\
c
\end{pmatrix}
=
\begin{pmatrix}
a+qc \\
c
\end{pmatrix},
\\
S
\begin{pmatrix}
a \\
c
\end{pmatrix}
&=
\begin{pmatrix}
0 & -1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a \\
c
\end{pmatrix}
=
\begin{pmatrix}
-c \\
a
\end{pmatrix}.
\end{align*}
If $c=0$, then $\gcd(a,0)=1$ forces $a \in \{1,-1\}$, and the claim holds with $w=I$.
Assume $c \neq 0$. Choose $q \in \mathbb{Z}$ and $r \in \mathbb{Z}$ such that
\begin{align*}
r = a + qc,
\qquad
|r| < |c|.
\end{align*}
This is the Euclidean division step applied to $a$ modulo $c$, with the sign absorbed into the choice of $q$. Then
\begin{align*}
S T^q
\begin{pmatrix}
a \\
c
\end{pmatrix}
=
S
\begin{pmatrix}
r \\
c
\end{pmatrix}
=
\begin{pmatrix}
-c \\
r
\end{pmatrix}.
\end{align*}
The new second coordinate has absolute value $|r|$, strictly smaller than the old absolute value $|c|$. Repeating this reduction produces a finite sequence because the non-negative integer $|c|$ strictly decreases at each non-terminal stage. The process stops when the second coordinate is $0$.
Throughout the process the matrices used are products of $S$ and integer powers of $T$, hence lie in $H$. The greatest common divisor of the two coordinates is preserved by multiplication by $S$ and by $T^q$, since these matrices are invertible over $\mathbb{Z}$. Therefore the terminal vector has the form $(\varepsilon,0)^\top$ with $\varepsilon \in \{1,-1\}$. This proves the claim.
[/proof]
[guided]
Let $H := \langle S,T\rangle$. The reduction is the Euclidean algorithm written in matrix language. The matrix $T^q$ performs the elementary row operation
\begin{align*}
(a,c)^\top \mapsto (a+qc,c)^\top,
\end{align*}
while $S$ swaps the two entries up to a sign:
\begin{align*}
(a,c)^\top \mapsto (-c,a)^\top.
\end{align*}
Both operations preserve the greatest common divisor because they are invertible integer linear transformations.
We prove the precise reduction statement. Let $(a,c) \in \mathbb{Z}^2$ satisfy $\gcd(a,c)=1$. If $c=0$, then $\gcd(a,0)=|a|=1$, so $a=\varepsilon$ for some $\varepsilon \in \{1,-1\}$, and the identity matrix already sends $(a,c)^\top$ to $(\varepsilon,0)^\top$.
Now suppose $c \neq 0$. Choose integers $q$ and $r$ such that
\begin{align*}
r = a+qc,
\qquad
|r| < |c|.
\end{align*}
This is exactly the Euclidean step: we replace $a$ by a remainder modulo $c$ whose absolute value is smaller than $|c|$. Applying $T^q$ first and then $S$ gives
\begin{align*}
S T^q
\begin{pmatrix}
a \\
c
\end{pmatrix}
=
S
\begin{pmatrix}
a+qc \\
c
\end{pmatrix}
=
S
\begin{pmatrix}
r \\
c
\end{pmatrix}
=
\begin{pmatrix}
-c \\
r
\end{pmatrix}.
\end{align*}
The important feature is that the second coordinate has changed from $c$ to $r$, and $|r|<|c|$. Thus repeated application of this operation must terminate, because there is no infinite strictly decreasing sequence of non-negative integers.
At the terminal stage the second coordinate is $0$. Since every step was multiplication by a matrix in $H$, the total product is some $w \in H$. Since every step is invertible over $\mathbb{Z}$, the greatest common divisor remains $1$, so the terminal vector must be $(1,0)^\top$ or $(-1,0)^\top$. Hence there exist $w \in H$ and $\varepsilon \in \{1,-1\}$ such that
\begin{align*}
w
\begin{pmatrix}
a \\
c
\end{pmatrix}
=
\begin{pmatrix}
\varepsilon \\
0
\end{pmatrix}.
\end{align*}
[/guided]
[/step]
[step:Use column reduction to express an arbitrary determinant-one matrix as a word in $S$ and $T$]
Let
\begin{align*}
\gamma :=
\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}
\in SL_2(\mathbb{Z}).
\end{align*}
The determinant condition gives
\begin{align*}
ad-bc = 1.
\end{align*}
Hence every common divisor of $a$ and $c$ divides $ad-bc=1$, so $\gcd(a,c)=1$.
By the primitive column reduction claim, choose $w \in H$ and $\varepsilon \in \{1,-1\}$ such that
\begin{align*}
w
\begin{pmatrix}
a \\
c
\end{pmatrix}
=
\begin{pmatrix}
\varepsilon \\
0
\end{pmatrix}.
\end{align*}
Since the first column of $w\gamma$ is $w(a,c)^\top$, there exist integers $n$ and $\delta$ such that
\begin{align*}
w\gamma =
\begin{pmatrix}
\varepsilon & n \\
0 & \delta
\end{pmatrix}.
\end{align*}
Because $w,\gamma \in SL_2(\mathbb{Z})$, their product has determinant $1$. Therefore
\begin{align*}
1 = \det(w\gamma) = \varepsilon \delta,
\end{align*}
so $\delta=\varepsilon$. Thus
\begin{align*}
w\gamma =
\begin{pmatrix}
\varepsilon & n \\
0 & \varepsilon
\end{pmatrix}.
\end{align*}
If $\varepsilon=1$, then
\begin{align*}
w\gamma =
\begin{pmatrix}
1 & n \\
0 & 1
\end{pmatrix}
= T^n \in H.
\end{align*}
If $\varepsilon=-1$, then
\begin{align*}
w\gamma =
\begin{pmatrix}
-1 & n \\
0 & -1
\end{pmatrix}
=
-S^0T^{-n}
=
(-I)T^{-n}
=
S^2T^{-n}
\in H,
\end{align*}
where we used $S^2=-I$. In both cases $w\gamma \in H$. Since $w \in H$ and $H$ is a subgroup, $w^{-1} \in H$, and therefore
\begin{align*}
\gamma = w^{-1}(w\gamma) \in H.
\end{align*}
Because $\gamma \in SL_2(\mathbb{Z})$ was arbitrary, $SL_2(\mathbb{Z}) \subset H$. The reverse inclusion $H \subset SL_2(\mathbb{Z})$ holds from the definition of $H$ as a subgroup generated by elements of $SL_2(\mathbb{Z})$. Hence
\begin{align*}
SL_2(\mathbb{Z}) = H = \langle S,T\rangle.
\end{align*}
[guided]
Let
\begin{align*}
\gamma :=
\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}
\in SL_2(\mathbb{Z}).
\end{align*}
We want to prove that $\gamma$ is a word in $S$ and $T$. The first column is the place to start because the determinant equation
\begin{align*}
ad-bc=1
\end{align*}
implies $\gcd(a,c)=1$: any integer dividing both $a$ and $c$ also divides $ad$ and $bc$, hence divides $ad-bc=1$.
The primitive column reduction claim applies to $(a,c)$. Thus there are $w \in H$ and $\varepsilon \in \{1,-1\}$ such that
\begin{align*}
w
\begin{pmatrix}
a \\
c
\end{pmatrix}
=
\begin{pmatrix}
\varepsilon \\
0
\end{pmatrix}.
\end{align*}
Since multiplying $\gamma$ on the left multiplies each column by $w$, the first column of $w\gamma$ is $(\varepsilon,0)^\top$. Hence $w\gamma$ has the form
\begin{align*}
w\gamma =
\begin{pmatrix}
\varepsilon & n \\
0 & \delta
\end{pmatrix}
\end{align*}
for some $n,\delta \in \mathbb{Z}$.
Now the determinant condition determines the lower-right entry. Since $w$ and $\gamma$ both have determinant $1$, the product $w\gamma$ also has determinant $1$. Therefore
\begin{align*}
1=\det(w\gamma)=\varepsilon \delta.
\end{align*}
Because $\varepsilon \in \{1,-1\}$, this forces $\delta=\varepsilon$. Thus
\begin{align*}
w\gamma =
\begin{pmatrix}
\varepsilon & n \\
0 & \varepsilon
\end{pmatrix}.
\end{align*}
There are two cases. If $\varepsilon=1$, then
\begin{align*}
w\gamma =
\begin{pmatrix}
1 & n \\
0 & 1
\end{pmatrix}
= T^n,
\end{align*}
which lies in $H$. If $\varepsilon=-1$, then
\begin{align*}
w\gamma =
\begin{pmatrix}
-1 & n \\
0 & -1
\end{pmatrix}
=
(-I)
\begin{pmatrix}
1 & -n \\
0 & 1
\end{pmatrix}
=
S^2T^{-n},
\end{align*}
which also lies in $H$, because $S^2=-I$ and $T^{-n} \in H$.
Thus $w\gamma \in H$. Since $w \in H$ and $H$ is a subgroup, $w^{-1} \in H$, so
\begin{align*}
\gamma = w^{-1}(w\gamma) \in H.
\end{align*}
This proves every element of $SL_2(\mathbb{Z})$ lies in $H$. Since $H$ was generated by elements already in $SL_2(\mathbb{Z})$, we conclude
\begin{align*}
SL_2(\mathbb{Z})=\langle S,T\rangle.
\end{align*}
[/guided]
[/step]
[step:Pass the generators and relations to $PSL_2(\mathbb{Z})$]
Let
\begin{align*}
\pi: SL_2(\mathbb{Z}) \to PSL_2(\mathbb{Z})
\end{align*}
be the quotient homomorphism, and define
\begin{align*}
\bar{S} := \pi(S),
\qquad
\bar{T} := \pi(T).
\end{align*}
Since $SL_2(\mathbb{Z})=\langle S,T\rangle$ and $\pi$ is surjective, every element of $PSL_2(\mathbb{Z})$ is a word in $\bar{S}$ and $\bar{T}$. Hence
\begin{align*}
PSL_2(\mathbb{Z})=\langle \bar{S},\bar{T}\rangle.
\end{align*}
Applying the homomorphism $\pi$ to the relations $S^2=(ST)^3=-I$ gives
\begin{align*}
\bar{S}^2
=
\pi(S)^2
=
\pi(S^2)
=
\pi(-I)
=
\pi(I),
\end{align*}
and
\begin{align*}
(\bar{S}\bar{T})^3
=
\pi(ST)^3
=
\pi((ST)^3)
=
\pi(-I)
=
\pi(I).
\end{align*}
Therefore
\begin{align*}
\bar{S}^2=(\bar{S}\bar{T})^3=\pi(I),
\end{align*}
which is the identity element of $PSL_2(\mathbb{Z})$. This completes the proof.
[/step]
