[proofplan]
Set $v=sw$, so $\ell(w)=\ell(v)+1$ and $sv=w$. The proof first invokes the defining Kazhdan-Lusztig triangularity and bar-invariance characterization, together with the standard left multiplication formula for $C_sC_v$. Expanding that identity in the standard basis reduces the theorem to a coefficient computation using the Hecke multiplication rule for $T_sT_x$. The case $sy>y$ is obtained directly from the coefficient of $T_y$, while the case $sy<y$ is the standard left-descent cancellation consequence of the same multiplication identity and the Kazhdan-Lusztig degree bound.
[/proofplan]
[step:Use the Kazhdan-Lusztig multiplication identity for a simple left ascent]
Let
\begin{align*}
v:=sw.
\end{align*}
Since $sw<w$, we have $v<w$, $sv=w$, and
\begin{align*}
\ell(w)=\ell(v)+1.
\end{align*}
By the existence and triangular characterization of the Kazhdan-Lusztig basis [citetheorem:8467], the element $C_v$ is bar-invariant and has expansion
\begin{align*}
C_v=q^{-\ell(v)/2}\sum_{x\le v}P_{x,v}(q)T_x.
\end{align*}
Let $e\in W$ denote the identity element. Also
\begin{align*}
C_s=q^{-1/2}(T_e+T_s).
\end{align*}
We use the assumed standard Kazhdan-Lusztig simple-reflection multiplication formula: since $sv=w>v$, it gives
\begin{align*}
C_sC_v=C_{sv}+\sum_{\substack{z\in W:\ z<v,\ sz<z}}\mu(z,v)C_z.
\end{align*}
The finite indexing set is contained in the Bruhat interval $\{z\in W:z\le v\}$; its finiteness follows from the subword description of Bruhat intervals [citetheorem:8468]. Since $sv=w$, the formula is equivalently
\begin{align*}
C_w=C_sC_v-\sum_{\substack{z\in W:\ z<v,\ sz<z}}\mu(z,v)C_z.
\end{align*}
Substituting $v=sw$ gives the displayed $y$-independent identity
\begin{align*}
C_w=C_sC_{sw}-\sum_{\substack{z\in W:\ z<sw,\ sz<z}}\mu(z,sw)C_z.
\end{align*}
[guided]
The purpose of this step is to isolate the part of the proof that belongs to the Kazhdan-Lusztig basis itself. We define
\begin{align*}
v:=sw.
\end{align*}
The hypothesis $sw<w$ says precisely that left multiplication by $s$ decreases the length of $w$. Therefore $v=sw$ satisfies $sv=w$, and the Coxeter length relation is
\begin{align*}
\ell(w)=\ell(v)+1.
\end{align*}
The Kazhdan-Lusztig basis elements are characterized by two properties: they are invariant under the bar involution, and they are triangular with respect to the standard basis and Bruhat order. In the normalization used here, this means
\begin{align*}
C_v=q^{-\ell(v)/2}\sum_{x\le v}P_{x,v}(q)T_x.
\end{align*}
For a simple reflection $s$, the Bruhat interval below $s$ consists of $e$ and $s$, and the normalization gives
\begin{align*}
C_s=q^{-1/2}(T_e+T_s).
\end{align*}
We now use the assumed standard simple-reflection multiplication formula for the Kazhdan-Lusztig basis. It says that whenever $sv>v$,
\begin{align*}
C_sC_v=C_{sv}+\sum_{\substack{z\in W:\ z<v,\ sz<z}}\mu(z,v)C_z.
\end{align*}
The hypotheses needed for this formula are part of the formal statement: the Kazhdan-Lusztig basis is normalized as above, the degree bound defining the top coefficient $\mu(z,v)$ is available, and $sv=w>v$. The indexing set is finite because Bruhat intervals are finite; this follows from the subword description of Bruhat intervals [citetheorem:8468]. The coefficient $\mu(z,v)$ is the top possible coefficient of $P_{z,v}(q)$, and only those lower terms with $sz<z$ occur in this correction.
Since $sv=w$, the multiplication formula becomes
\begin{align*}
C_sC_v=C_w+\sum_{\substack{z\in W:\ z<v,\ sz<z}}\mu(z,v)C_z.
\end{align*}
Solving for $C_w$ gives
\begin{align*}
C_w=C_sC_v-\sum_{\substack{z\in W:\ z<v,\ sz<z}}\mu(z,v)C_z.
\end{align*}
Finally, replacing $v$ by $sw$ gives
\begin{align*}
C_w=C_sC_{sw}-\sum_{\substack{z\in W:\ z<sw,\ sz<z}}\mu(z,sw)C_z.
\end{align*}
This is the basis identity from which the polynomial recursion is obtained by taking the coefficient of $T_y$.
[/guided]
[/step]
[step:Expand the coefficient of $T_y$ in $C_sC_{sw}$]
Keep $v=sw$. From $C_s=q^{-1/2}(T_e+T_s)$ and the expansion of $C_v$,
\begin{align*}
C_sC_v=q^{-\ell(w)/2}\sum_{x\le v}P_{x,v}(q)(T_x+T_sT_x).
\end{align*}
For $x\in W$, the left multiplication rule in the Hecke algebra is
\begin{align*}
T_sT_x=T_{sx}
\end{align*}
if $sx>x$, and
\begin{align*}
T_sT_x=qT_{sx}+(q-1)T_x
\end{align*}
if $sx<x$.
Let $A_y(q)\in \mathbb Z[q]$ denote the coefficient of $T_y$ inside the parenthesized standard-basis expansion of $C_sC_v$, after the common factor $q^{-\ell(w)/2}$ has been removed. If $sy>y$, then the contribution from $T_x$ occurs at $x=y$, and the contribution from $T_sT_x$ occurs at $x=sy$, with $s(sy)=y<sy$. Therefore
\begin{align*}
A_y(q)=P_{y,v}(q)+qP_{sy,v}(q).
\end{align*}
If $sy<y$, then the terms contributing to $T_y$ are $x=y$, the $(q-1)T_y$ part of $T_sT_y$, and the $T_y$ part of $T_sT_{sy}$; hence
\begin{align*}
A_y(q)=qP_{y,v}(q)+P_{sy,v}(q).
\end{align*}
[/step]
[step:Subtract the lower Kazhdan-Lusztig basis corrections]
For each $z\in W$, the coefficient of $T_y$ in $C_z$ is
\begin{align*}
q^{-\ell(z)/2}P_{y,z}(q),
\end{align*}
with the convention that $P_{y,z}(q)=0$ if $y\nleq z$. Rewriting this coefficient with the common factor $q^{-\ell(w)/2}$ gives
\begin{align*}
q^{-\ell(z)/2}P_{y,z}(q)=q^{-\ell(w)/2}q^{(\ell(w)-\ell(z))/2}P_{y,z}(q).
\end{align*}
Taking the coefficient of $T_y$ in
\begin{align*}
C_w=C_sC_v-\sum_{\substack{z\in W:\ z<v,\ sz<z}}\mu(z,v)C_z
\end{align*}
therefore gives
\begin{align*}
P_{y,w}(q)=A_y(q)-\sum_{\substack{z\in W:\ y\le z<v,\ sz<z}}\mu(z,v)q^{(\ell(w)-\ell(z))/2}P_{y,z}(q).
\end{align*}
Since $v=sw$, this is
\begin{align*}
P_{y,w}(q)=A_y(q)-\sum_{\substack{z\in W:\ y\le z<sw,\ sz<z}}\mu(z,sw)q^{(\ell(w)-\ell(z))/2}P_{y,z}(q).
\end{align*}
The exponent may be half-integral, because the calculation takes place in $\mathbb Z[q^{1/2},q^{-1/2}]$; the final equality is nevertheless an equality whose left-hand side lies in $\mathbb Z[q]$, and the Kazhdan-Lusztig degree bound is exactly what makes the cancellation compatible with the polynomial normalization.
[/step]
[step:Read off the recurrence when $sy>y$]
Assume $sy>y$. From the coefficient computation,
\begin{align*}
A_y(q)=P_{y,sw}(q)+qP_{sy,sw}(q).
\end{align*}
Substituting this value of $A_y(q)$ into the coefficient identity gives
\begin{align*}
P_{y,w}(q)=qP_{sy,sw}(q)+P_{y,sw}(q)-\sum_{\substack{z\in W:\ y\le z<sw,\ sz<z}}\mu(z,sw)q^{(\ell(w)-\ell(z))/2}P_{y,z}(q).
\end{align*}
This is the asserted recursion in the case $sy>y$.
[/step]
[step:Use the assumed left-descent cancellation when $sy<y$]
Assume $sy<y$. The same coefficient identity gives
\begin{align*}
P_{y,w}(q)=qP_{y,sw}(q)+P_{sy,sw}(q)-\sum_{\substack{z\in W:\ y\le z<sw,\ sz<z}}\mu(z,sw)q^{(\ell(w)-\ell(z))/2}P_{y,z}(q).
\end{align*}
The formal statement includes the left-descent cancellation consequence of the Kazhdan-Lusztig multiplication formula. Applying it with $v=sw$ is legitimate because $sy<y$ by the present case assumption and $sv=s(sw)=w>sw=v$ by $sw<w$. Hence
\begin{align*}
qP_{y,sw}(q)=\sum_{\substack{z\in W:\ y\le z<sw,\ sz<z}}\mu(z,sw)q^{(\ell(w)-\ell(z))/2}P_{y,z}(q).
\end{align*}
Substituting this cancellation identity into the previous display yields
\begin{align*}
P_{y,w}(q)=P_{sy,sw}(q).
\end{align*}
This proves the asserted recursion in the case $sy<y$.
[guided]
Assume $sy<y$. From the coefficient extraction already proved, the coefficient of $T_y$ in the basis identity gives
\begin{align*}
P_{y,w}(q)=qP_{y,sw}(q)+P_{sy,sw}(q)-\sum_{\substack{z\in W:\ y\le z<sw,\ sz<z}}\mu(z,sw)q^{(\ell(w)-\ell(z))/2}P_{y,z}(q).
\end{align*}
The only term preventing the desired formula is the extra summand $qP_{y,sw}(q)$, so we use the left-descent cancellation identity that has been made an explicit hypothesis of the theorem. Its hypotheses are satisfied here: the present case gives $sy<y$, and if $v:=sw$, then $sv=s(sw)=w$ and $sw<w$ implies $v<w=sv$. Therefore the cancellation identity applied to $y$, $v=sw$, and $s$ gives
\begin{align*}
qP_{y,sw}(q)=\sum_{\substack{z\in W:\ y\le z<sw,\ sz<z}}\mu(z,sw)q^{(\ell(w)-\ell(z))/2}P_{y,z}(q).
\end{align*}
Substituting this equality into the coefficient formula cancels the entire correction sum against $qP_{y,sw}(q)$, leaving exactly
\begin{align*}
P_{y,w}(q)=P_{sy,sw}(q).
\end{align*}
This is the first branch of the Kazhdan-Lusztig polynomial recursion.
[/guided]
[/step]
[step:Combine the two cases]
The alternatives $sy<y$ and $sy>y$ are exhaustive for $s\in S$ because left multiplication by a simple reflection changes the Coxeter length by exactly $1$. The previous two steps prove the displayed formula in each case. The basis identity was proved before coefficient extraction, so the equivalent $y$-independent Kazhdan-Lusztig identity also holds. This completes the proof.
[/step]
