Solution:
We have to prove
$$\sum_{j=1}^{n} \frac{1}{1+x_{j}}-\sum_{j=1}^{n} \frac{x_{j}}{1+x_{j}^{2}}=\sum_{j=1}^{n} \frac{1-x_{j}}{\left(1+x_{j}\right)\left(1+x_{j}^{2}\right)} \geqslant 0$$
We use the supporting line method and consider the function $f$ defined by
$$f(x)=\frac{1-x}{(1+x)\left(1+x^{2}\right)}$$
for all $x>-1$. The tangent line of $f$ at $x=1$ is given by $y=\frac{1-x}{4}$. We claim that
$$f(x)=\frac{1-x}{(1+x)\left(1+x^{2}\right)} \geqslant \frac{1-x}{4}$$
for all $x>-1$ with equality for $x=1$. For $x \geqslant 1$ we get $4 \leqslant(1+x)\left(1+x^{2}\right)$ and for $-1<x \leqslant 1$ we get $4 \geqslant(1+x)\left(1+x^{2}\right)$. Both inequalities are obviously true.

Now we conclude that
$$\sum_{j=1}^{n} \frac{1-x_{j}}{\left(1+x_{j}\right)\left(1+x_{j}^{2}\right)} \geqslant \sum_{j=1}^{n} \frac{1-x_{j}}{4}=0$$
and we are done.

Equality occurs if and only if all $n$ numbers are equal to 1 .

Solution:
Since $1+x_{j}>0$ for $j=1,2, \ldots, n$, Cauchy-Schwarz inequality yields
$$\sum_{j=1}^{n} \frac{1}{1+x_{j}} \cdot \sum_{j=1}^{n}\left(1+x_{j}\right) \geqslant\left(\sum_{j=1}^{n} 1\right)^{2}$$
which is equivalent to
$$\sum_{j=1}^{n} \frac{1}{1+x_{j}} \geqslant \frac{n}{2}$$
It therefore suffices to prove that
$$\sum_{j=1}^{n} \frac{x_{j}}{1+x_{j}^{2}} \leqslant \frac{n}{2}$$
but this last inequality is equivalent to the trivial one
$$\sum_{j=1}^{n} \frac{\left(1-x_{j}\right)^{2}}{1+x_{j}^{2}} \geqslant 0$$
so the inequation is proven.
In the last equation, we have equality if and only if $x_{j}=1$ for $j=1,2, \ldots, n$, and one can easily see that this is indeed a case of equality, so it is the only case of equality.

Solution:
The inequality is equivalent to
$$\sum_{i=1}^{n} \frac{1-x_{i}}{\left(1+x_{i}\right)\left(1+x_{i}^{2}\right)} \geqslant 0$$
As the functions $f(x)=1-x$ and $g(x)=\frac{1}{(1+x)\left(1+x^{2}\right)}$ are both strictly decreasing, we can apply the Chebychev inequality to obtain:
$$n \cdot \sum_{i=1}^{n} \frac{1-x_{i}}{\left(1+x_{i}\right)\left(1+x_{i}^{2}\right)} \geqslant\left(\sum_{i=1}^{n} 1-x_{i}\right)\left(\sum_{i=1}^{n} \frac{1}{\left(1+x_{i}\right)\left(1+x_{i}^{2}\right)}\right)=0$$
So we're done.

Solution (via Lagrange multipliers):
Let us write $f(x)=\frac{1}{1+x}-\frac{x}{1+x^{2}}$. We want to show that the expression $f\left(x_{1}\right)+\ldots+f\left(x_{n}\right)$ in the domain
$$D: x_{1}, \ldots, x_{n}>-1, x_{1}+\ldots+x_{n}=n$$
attains its minimal value 0 exactly at the point $x_{1}=\ldots=x_{n}=1$.
We first consider the boundary of $D$. This means that w. l. o. g. we may assume that $x_{1}=-1$, in which case the expression attains the value $+\infty$, which is not the minimum.
We now look for minima in the interior of the domain: The method of Lagrange multipliers gives the Langrange function
$$F\left(x_{1}, \ldots, x_{n}, \lambda\right)=\sum_{j=1}^{n}\left(f\left(x_{j}\right)-\lambda\left(x_{j}-1\right)\right)$$
and results in the system of equations
$$\begin{aligned} f^{\prime}\left(x_{j}\right) & =\lambda, \quad j=1, \ldots, n \\ \sum_{j=1}^{n} x_{j} & =n \end{aligned}$$
Now note that
- $f^{\prime}(x)=\frac{-1}{(1+x)^{2}}+\frac{x^{2}-1}{\left(1+x^{2}\right)^{2}}=\frac{2\left(x^{3}-x^{2}-x-1\right)}{(1+x)^{2}\left(1+x^{2}\right)^{2}}$.
- $f^{\prime}(x)<0$ for $-1<x \leqslant 1$. This is obvious from the first expression for $f^{\prime}(x)$.
- $f^{\prime}(x)>0$ for $x>2$. This can be seen from the second expression for $f^{\prime}(x)$, since for $x>2$ we have $1+x+x^{2}<\frac{x^{3}}{8}+\frac{x^{3}}{4}+\frac{x^{3}}{2}<x^{3}$.
- $f^{\prime \prime}(x)=\frac{2 x\left(3-x^{2}\right)}{\left(1+x^{2}\right)^{3}}+\frac{2}{(1+x)^{3}}$.
- $f^{\prime \prime}(x)>0$ for $-1<x<2$ can be shown by considering the following three cases:
- For $-1<x<0$, we have
$$\frac{1}{(1+x)^{3}}=\frac{1}{(1+x)\left(1+2 x+x^{2}\right)}>\frac{1}{(1+x)\left(1+x^{2}\right)}$$
Thus we get
$$\begin{aligned} & f^{\prime \prime}(x)> \frac{2 x\left(3-x^{2}\right)}{\left(1+x^{2}\right)^{3}}+\frac{2}{(1+x)\left(1+x^{2}\right)}=\frac{2 x\left(3-x^{2}\right)(1+x)+2\left(1+x^{2}\right)^{2}}{(1+x)\left(1+x^{2}\right)^{3}}= \\ &= \frac{\left(6 x+6 x^{2}-2 x^{3}-2 x^{4}\right)+\left(2+4 x^{2}+2 x^{4}\right)}{(1+x)\left(1+x^{2}\right)^{3}}=\frac{2+6 x+10 x^{2}-2 x^{3}}{(1+x)\left(1+x^{2}\right)^{3}}= \\ &=\frac{\frac{1}{2}(2+3 x)^{2}+\frac{11}{2} x^{2}-2 x^{3}}{(1+x)\left(1+x^{2}\right)^{3}}>0 \end{aligned}$$
- For $0 \leqslant x \leqslant \sqrt{3}$, the assertion is obvious.
- For $\sqrt{3}<x<2$, the assertion follows from
$$\frac{2}{(1+x)^{3}}>\frac{2}{27}, \quad \frac{2 x\left(3-x^{2}\right)}{\left(1+x^{2}\right)^{3}}=-\frac{2 x\left(x^{2}-3\right)}{\left(1+x^{2}\right)^{3}}>-\frac{2 \cdot 2\left(2^{2}-3\right)}{\left(1+\sqrt{3}^{2}\right)^{3}}=-\frac{1}{16}>-\frac{2}{27}$$
- Hence $f^{\prime}$ is strictly increasing for $-1<x \leqslant 2$.
Since $\bar{x}=\frac{1}{n} \sum_{j=1}^{n} x_{j}=1$, we know that $x_{j} \leqslant 1$ for some $j$. Therefore $\lambda<0$. This means $x_{j} \leqslant 2$ for every $j=1, \ldots, n$. From the monotonicity of $f^{\prime}$ in the domain $-1<x \leqslant 2$, we now conclude $x_{1}=\ldots=x_{n}$. In view of the condition $x_{1}+\ldots+x_{n}=n$ this means $x_{1}=\ldots=x_{n}=1$. Since $f(1)=0$, we are done.