[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*}[/step]

[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: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$.[/step]

[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: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]