Solution
= Solution
The defining minimization, compared with the candidate $x_k$, shows that $f(x_{k+1})\leq f(x_k)$. Put $u=x^*$ in part ii and sum from $j=0$ to $k-1$. The squared distances telescope, while monotonicity gives
$$
kt[f(x_k)-f^*]
\leq t\sum_{j=0}^{k-1}[f(x_{j+1})-f^*]
\leq\frac12\|x_0-x^*\|^2.
$$
Hence
$$
\boxed{f(x_k)-f^*\leq\frac{\|x_0-x^*\|^2}{2kt}.}
$$