Proving Lipschitz gradient of $f(x)=\sqrt{1+\|x\|^2}$ 
Given $f(x)=\sqrt{1+\|x\|^2}$ and $f:\mathbb{R}^n\to\mathbb{R}$. Prove $f\in C_1^{1,1}$, meaning$$\|\nabla f(x)-\nabla f(y)\|\leq\|x-y\|.$$

I've tried to see how to prove it for $n=2$ but got stuck at computing the norm of the hessian. I know if I can prove $\|\nabla^2f(x)\|_2\leq 1$ will be enough.
I know that $\nabla f(x)=\frac{x}{\sqrt{1+\|x\|^2}}$ i thought maybe i can assume w.l.o.g that $\|x\|\geq \|y\|$ to prove this.
 A: You already found that the first order derivatives are
$$
\partial_i f(x)
=
\frac{x_i}{\sqrt{1+\|x\|^2}}.
$$
Differentiating again gives
$$
\partial_j\partial_i f(x)
=
\frac{\delta_{ij}}{\sqrt{1+\|x\|^2}}
-
\frac{x_ix_j}{(1+\|x\|^2)^{3/2}}
.
$$
Thus if I denote $a=1/\sqrt{1+\|x\|^2}$, then the Hessian is
$$
\nabla^2f(x)
=
aI-a^3xx^T.
$$
We want to operate with this on any vector $v$.
It helps to split $v=v_\parallel+v_\perp$, so that $v_\parallel$ is parallel to $x$ and $v_\perp$ orthogonal to it.
(Check what happens to these parts when you operate on them by the matrix $xx^T$! It is quite simple to check, and I urge you to do it yourself to see what is going on.)
We get
$$
(aI-a^3xx^T)(v_\parallel+v_\perp)
=
(a-a^3\|x\|^2)v_\parallel
+
(a-0)v_\perp.
$$
Now $a-a^3\|x\|^2=a^3(1+\|x\|^2-\|x\|^2)=a^3$, so we have simply
$$
\nabla^2f(x)v
=
a^3v_\parallel
+
av_\perp.
$$
Thus with $a\leq1$ we get
$$
\|\nabla^2f(x)v\|^2
=
a^6\|v_\parallel\|^2
+
a^2\|v_\perp\|^2
\leq
\|v_\parallel\|^2
+
\|v_\perp\|^2
=
\|v\|^2.
$$
This is exactly the estimate for the Hessian that you were after.
