I think induction over $T$ will be hard. But you can prove the inequality by considering the times $n$ at which the maximum $\bar s_n$ increases. For example, let
$
1 = k_1, \ldots, k_r \le T
$
be the different times at which $s_k = \bar s_k$ attains a maximum (with respect to all previous times). Then it holds
$$
\sum_{l=k_j}^{k_{j+1}-1} \bar s_l (s_{l+1} - s_l) = \sum_{l=k_j}^{k_{j+1}-1} \bar s_{k_j} (s_{l+1} - s_l) = \bar s_{k_j} (\bar s_{k_{j+1}} - \bar s_{k_j} ).
$$
Therefore we see that
$$
\bar s_T^2 + 4\sum_{n=1}^{T-1} \bar s_n (s_{n+1} - s_n) = \bar s_{k_r}^2 + 4\sum_{j=1}^{r-1} \bar s_{k_j} (\bar s_{k_{j+1}} - \bar s_{k_j} ) + 4\bar s_{k_r} (s_T - \bar s_{k_r})
$$
Since the $\bar s_{k_j}$ are increasing, we estimate the right hand side by
$$
\bar s_{k_r}^2 + 2\sum_{j=1}^{r-1} (\bar s_{k_{j+1}} + \bar s_{k_j}) (\bar s_{k_{j+1}} - \bar s_{k_j} ) + 4\bar s_{k_r} (s_T - \bar s_{k_r})
$$
which by the third binomial formula yields
$$
\bar s_{k_r}^2 + 2\sum_{j=1}^{r-1} (\bar s_{k_{j+1}}^2 - \bar s_{k_j}^2) + 4\bar s_{k_r} (s_T - \bar s_{k_r}) = \bar s_{k_r}^2 + 2(\bar s_{k_{r}}^2 - \bar s_{1}^2) + 4\bar s_{k_r} (s_T - \bar s_{k_r}).
$$
Obviously, this is bounded by
$$
-\bar s_{k_r}^2 + 4\bar s_{k_r} s_T = -(\bar s_{k_r} - 2s_T)^2 + 4s_T^2 \le 4s_T^2,
$$
which finishes the proof. For comparison, also refer to the proof of Lemma 2.2 in the paper you quoted.