Concavity inequality for the matrix square root Let $A$, $B$ and $C$ be symmetric, positive semi-definite matrices. Is it true that
$$ \|(A + C)^{1/2} - (B + C)^{1/2}\| \leq \|A^{1/2} - B^{1/2}\|,$$
in either the 2 or Frobenius norm? 
It is clearly true when $A, B$ and $C$ commute, but the general case is less clear to me. In fact, even the particular case $B = 0$ does not seem obvious.

Without loss of generality, it is clear that we can assume that $C$ is diagonal.
We show that it is sufficient to prove to prove the inequality for the matrix with zeros everywhere except on any position $k$ on the diagonal,
$$
(C_k)_{ij} = \begin{cases} 1 & \text{if } i=j=k\\ 0 & \text{otherwise} \end{cases}
$$
Clearly,  if the inequality is true for one $C_k$, it is true for any $C_k$, by flipping the axes, and also for $C = \alpha C_k$, for any $\alpha \geq 0$, because
\begin{align}
\|(A + \alpha \, C_k)^{1/2} - (B + \alpha C_k)^{1/2}\| 
&= \sqrt{\alpha} \|(A/\alpha +  C_k)^{1/2} - (B/\alpha + C_k)^{1/2}\|  \\
&\leq \sqrt{\alpha} \|(A/\alpha)^{1/2} - (B/\alpha)^{1/2}\|
= \sqrt{\alpha} \|A^{1/2} - B^{1/2}\|
\end{align}
Now, a general diagonal $C$ can be decomposed as $C = \sum_{k=1}^{n} \alpha_k C_k$.
Applying the previous inequality (specialized for a matrix $C$ with only one nonzero diagonal element) repeatedly,
we can remove the diagonal elements one by one
\begin{align}
&\|(A + \sum_{k=1}^{n}\alpha_k \, C_k)^{1/2} - (B + \sum_{k=1}^{n}\alpha_k \, C_k)^{1/2}\| \\
&\qquad = \|((A + \sum_{k=1}^{n-1}\alpha_k \, C_k) + \alpha_n C_n)^{1/2} - ((B + \sum_{k=1}^{n-1}\alpha_k \, C_k) + \alpha_n C_n)^{1/2}\| \\
&\qquad \leq \|(A + \sum_{k=1}^{n-1}\alpha_k \, C_k)^{1/2} - (B + \sum_{k=1}^{n-1}\alpha_k \, C_k)^{1/2}\| \\
&\qquad \leq \|(A + \sum_{k=1}^{n-2}\alpha_k \, C_k)^{1/2} - (B + \sum_{k=1}^{n-2}\alpha_k \, C_k)^{1/2}\| \\
&\qquad \leq \dots \leq \sqrt{\alpha} \|A^{1/2} - B^{1/2}\|.
\end{align}

Here are three ways of proving the inequality in 1 dimension,
which I tried to generalize to the multidimensional case without success.
Let us write $a$, $b$, $c$ instead of $A$, $B$, $C$,
to emphasize that we are working in one dimension,
and let us assume without loss of generality that $a \leq b$.


*

*Let us write:
$$ f(c) = \sqrt{b + c} - \sqrt{a + c} $$
We calculate that the derivative of $f$ is given by
$$
f'(c) = \frac{1}{2} \left( \frac{1}{\sqrt{b + c}} - \frac{1}{\sqrt{a + c}} \right) \leq 0,
$$
and so $f(c) = f(0) + \int_{0}^{c} f'(x) \, d x  \leq f(0)$.

*We have, by the fundamental theorem of calculus and a change of variable
\begin{align}
    \sqrt{b + c} - \sqrt{a + c} &= \int_{a + c}^{b + c} \frac{1}{2 \sqrt{x}} \, d x = \int_{a}^{b} \frac{1}{2 \sqrt{x + c}} \, d x  \\
    &\leq \int_{a}^{b} \frac{1}{2 \sqrt{x}} \, d x = \sqrt{b} - \sqrt{a}.
\end{align}

*Squaring the two sides of the inequality, we obtain
$$
a + c - 2 \sqrt{a+ c} \, \sqrt{b + c} + b + c \leq a + b - 2 \sqrt{a} \sqrt{b}.
$$
Simplifying and rearranging,
$$
c + \sqrt{a} \sqrt{b} \leq \sqrt{a+ c} \, \sqrt{b + c} .
$$
Squaring again
$$
\require{cancel} \cancel{c^2 + a b} + 2 c \sqrt{a b} \leq \cancel{c^2 + ab} + ac + bc,
$$
leading to
$$ a  + b - 2 \sqrt{ab} = (\sqrt{b} - \sqrt{a})^2 \geq 0$$.
Numerical experiments suggest that the inequality is true in both the 2 and the Frobenius norm. 
(One realization of) the following code prints 0.9998775.
import numpy as np
import scipy.linalg as la

n, d, ratios = 100000, 3, []
for i in range(n):
    A = np.random.randn(d, d)
    B = np.random.randn(d, d)
    C = .1*np.random.randn(d, d)
    A, B, C = A.dot(A.T), B.dot(B.T), C.dot(C.T)
    lhs = la.norm(la.sqrtm(A + C) - la.sqrtm(B + C), ord='fro')
    rhs = la.norm(la.sqrtm(A) - la.sqrtm(B), ord='fro')
    ratios.append(lhs/rhs)

print(np.max(ratios))

 A: Here is a partial answer, showing that 
$$ \|(A + C)^{1/2} - (B + C)^{1/2}\| \leq c \|A^{1/2} - B^{1/2}\|,$$
for a constant $c$ that depends only on the dimension of the problem.
Below, $c$ denotes any constant that depends only on the dimension, and it can change from line to line.
Step 1: we show that, for symmetric positive semi-definite matrices,
$$
d(A, B) = \sup_{\|x\| = 1} \left| \|Ax\| - \|Bx\| \right| = \sup_{\|x\| = 1} \left| \sqrt{x^TA^2 x} - \sqrt{x^T B^2 x} \right| 
$$
defines a distance equivalent to any matrix norm. We show this for the usual 2-norm. It is showed in this post that
$$ \| A - B \| \leq C\,  d(A, B), $$
for a constant $C$ depending only on the dimension, so we have to show only that
$$
d(A, B) \leq C \| A-B \|,
$$
which follows from taking the suppremum in the following equation,
where we employ the triangle inequality:
$$
| \|Ax\| - \|Bx\| | \leq \|Ax - Bx\| = \|(A - B)x\| \leq \|A -B\| \|x\| = \|A - B\|.
$$
Step 2: In view of Step 1, it is sufficient to show
$$
d( (A + C)^{1/2}, (B + C)^{1/2} ) \leq d(A^{1/2}, B^{1/2}),
$$
which in turn will follow from
$$
\left| \sqrt{x^T (A + C) x} - \sqrt{x^T (B + C) x} \right| \leq \left| \sqrt{x^TA x} - \sqrt{x^T B x} \right|.
$$
Letting $a = x^TAx$, $b = x^T B x$, and $c = x^T C x$, this equation can be rewritten as
$$
\left| \sqrt{a+c} - \sqrt{b + c} \right| \leq \left| \sqrt{a} - \sqrt{b} \right|,
$$
which we know is true from the one-dimensional case.
A: Not an answer. I would like to discuss some equivalent problems.
Let $\mathbb{S}^n_{\succeq 0}$ denote the set of $n\times n$ real symmetric positive semi-definite matrices.
We have
\begin{align}
&\|(A+C)^{1/2} - (B+C)^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \quad \forall A, B, C \in \mathbb{S}^n_{\succeq 0} \tag{1}\\
\Leftrightarrow \quad &\|(A+uu^T)^{1/2} - (B+uu^T)^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \quad \forall A, B\in \mathbb{S}^n_{\succeq 0}, \quad \forall u\in \mathbb{R}^n\tag{2}\\
\Leftrightarrow \quad
&\|(A+\mathrm{diag}(u^Tu, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(u^Tu, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \\
&\qquad \forall A, B\in \mathbb{S}^n_{\succeq 0}, \quad \forall u\in \mathbb{R}^n\tag{3}\\
\Leftrightarrow \quad
&\|(A+\mathrm{diag}(1, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(1, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|,\\
& \qquad \forall A, B\in \mathbb{S}^n_{\succeq 0}.\tag{4}
\end{align}
Thus, it suffices to prove that
$$\|(A+\mathrm{diag}(1, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(1, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|.$$
