Stopped running sum of uniform random variables $\sum_{j=1}^k\frac{X_j}{2^j}$ This is a question on one of the official solutions to problem A4 in Putnam 2022. The problem and its solutions can be found here. My question is about Solution 1 to A4.
$X_1, X_2, \ldots$ is a sequence of iid r.v. with uniform distribution on $(0,1)$.
Define the stopping time $k$
$$k = \min\{n \geq 1: X_{n+1} > X_n\}$$
and the random variable $S$
$$S = \sum_{j=1}^k\frac{X_j}{2^j}$$
The problem is asking for the value of $E[S]$.
Assuming that I understood it correctly, Solution 1 goes as follows. It first defines
$$F(x) := E[S1_{X_1 \leq x}]$$
Then it asserts
$$E[S1_{X_1 \leq x}\mid X_1 = u] = \begin{cases}0 & u > x \\ \frac{u}{2} + \frac{1}{2}E[S1_{X_1 \leq u}] & u \leq x \end{cases}$$
I don't see how to arrive at the expression for the case $u \leq x$. The $\frac{u}{2}$ part is clear. Where does $E[S1_{X_1 \leq u}]$ come from?
 A: Here is also "a 'first-step analysis' that expresses the expected value for the sum starting with $X_1$ in terms of the expected value for the sum starting with $X_2$".  It is basically a slightly-easier version of the official solution 1.
Let $k_X=\min\{n\ge1:X_{n+1}>X_n\}$.
Let $g(u)=E[S|X_1=u]$. Then
$$\begin{aligned}
g(u)&=E\left[\left.\sum_{j=1}^{k_X}\frac{X_j}{2^j}\right|X_1=u\right]\\
&=E\left[\frac u2+\sum_{j=2}^{k_X}\frac{X_j}{2^j}\right]\\
(\text{Let } Y_i=X_{i+1})\quad&=E\left[\frac u2+\frac12\sum_{i=1}^{k_Y}\frac{Y_i}{2^i}\right]\\
&=\frac u2+\frac12E\left[\sum_{i=1}^{k_Y}\frac{Y_i}{2^i}\right]\\
&=\frac u2+\frac12\int_{y_1=0}^{1}[k_Y>0]g(y_1)\,\text dy_1\\
&=\frac u2+\frac12\int_{y_1=0}^{u}g(y_1)\,\text dy_1\\
\end{aligned}$$
where
$k_Y=\begin{cases}
0&\text{if }Y_1>u,\\
\min\{n\ge1:Y_{n+1}>Y_n\}&\text{otherwise.}\end{cases}$ and
the Iverson bracket $[K_Y>0]=\begin{cases}
0&\text{if }Y_1>u,\\
1&\text{otherwise.}\end{cases}\ $
We can see that besides $u/2$, there are contributions to $S$ that come from $X_2,X_3,\cdots$ or what are the same, $Y_1, Y_2, \cdots$. That basically also explains "where does $E[S1_{X_1 \leq u}]$ come  from?" in the question.
The equality above implies the differential equation
$g'(u)-g(u)/2=1/2$
with initial condition $g(0)=0$.
Hence $g(u)=e^{u/2}-1$.
$E[S]=\int_{u=0}^{1}E[S|X_1=u]\,\text du=\left.(2e^{u/2}-u)\right|_{u=0}^1=2\sqrt e-3.$
