I have been struggling to prove the following inequality given in this paper–please see eq. (34)

$$f(x^{k+1}) leq f(x) + (x^{k+1}-x)^Tnabla f(x^{k}) + frac{L}{2}|x^{k+1} – x^k|$$ for an iterative scheme — ADMM — where $f$ is a convex function whose gradient is $L$-Lipschitz and $k$ is an iteration number.

Although they show some proof but I can barely follow. Please help to clarify this proof. Below I have pasted for your convenience.

begin{align}

f(x) – f(x^{k+1}) – left( x – x^{k+1} right)^T nabla f(x^{k}) &geq ? tag 1\

f(x^{k}) + left( x – x^{k} right)^T nabla f(x^{k})

– f(x^{k+1}) – left( x – x^{k+1} right)^T nabla f(x^{k}) &= ? tag 2\

f(x^{k}) – f(x^{k+1}) – left( x – x^{k+1} right)^T nabla f(x^{k}) &geq frac{-L}{2} | x^{k+1} – x^{k} |^2 tag 3

end{align}

How did they achieve $(1)$ and also $frac{-L}{2} | x^{k+1} – x^{k} |^2 $ ?

From the Lipschitz condition, the bound that can be used as a starting point is

begin{align}

f(y) leq f(x) + left( y – x right)^T nabla f(x) + frac{L}{2} | y – x |_2^2.

end{align}

If I set $y = x^{k+1}$ and $x = x^{k}$, then we have

begin{align}

f(x^{k+1}) leq f(x^{k}) + left( x^{k+1} – x^{k} right)^T nabla f(x^{k}) + frac{L}{2} | x^{k+1} – x^{k} |_2^2.

end{align}

Then, what to do? Can someone please enlighten me and show the steps in between? I would be so grateful to you.