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.
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.