Interested by this problem which ask for the solution of
$$f_n(x)=x^x-(x-n)^{x+n}$$ that I rewrote as
$$g(x)=x\log(x)-(x+n)\log(x-n)$$ After two series expansions, I obtained, for large $n$, as a very first estimate
$$x_n^{(0)}=n+\sqrt n+\frac 14 \log(n)+\frac 12 \tag 1$$ which does not seem to be too bad
$$
\left(
\begin{array}{ccc}
k & x_{10^k}^{(0)} & x_{10^k} \\
1 & 14.2379239334 & 15.1346725729 \\
2 & 111.651292546 & 112.116435031 \\
3 & 1033.84971542 & 1034.08264064 \\
4 & 10102.8025851 & 10102.9137478 \\
5 & 100319.605997 & 100319.656436 \\
6 & 1001003.95388 & 1001003.97574 \\
7 & 10003166.8072 & 10003166.8163 \\
8 & 100010005.105 & 100010005.109
\\\end{array}
\right)$$
We have $\forall n$
$$g\big(x_n^{(0)} \big) ~>~ 0 \qquad \qquad g'\big(x_n^{(0)} \big)~<~0 \qquad\qquad g''\big(x_n^{(0)} \big)~> ~0$$ So, by Darboux theorem, we know that this is an underestimate of the solution which, then, will be reached without any overshoot.
Using this estimate, the $\color{red}{\text{first}}$ iterate of Newton-like methods of order $p$ is fully explicit (even if messy). For illustration of the worst case where $n=10$
$$\left(
\begin{array}{cc}
p & x_{10}^{(1)} & \text{method} \\
2 & 15.0400117306 & \text{Newton} \\
3 & 15.1375069522 & \text{Halley} \\
4 & 15.1343850068 & \text{Householder} \\
5 & 15.1347106313 & \text{no name} \\
6 & 15.1346668689 & \text{no name} \\
7 & 15.1346734910 & \text{no name} \\
8 & 15.1346724180 & \text{no name} \\
\cdots & \cdots & \\
\infty & 15.1346725729 & \text{solution} \\
\end{array}
\right)$$
My question is : what could be the next term(s) in $(1)$ to make it better for small values of $n$ ?
Any idea idea or suggestion would be really welcome. Thanks in advance.
Edit (after @Empy2's answer)
If we compute the first iterate of Newton method and expand it for large values of $n$, we have
$$x_n^{(1)}-x_n^{(0)}=\frac {3 \log ^2(n)+8 \log (n)+12 }{32 \sqrt{n} }+O\left(\frac{1}{n}\right)$$
which is exactly what @Empy2 answered.
The good thing is $g\big(x_n^{(1)} \big)$ is still positive.
Repeating the calculations
$$
\left(
\begin{array}{ccc}
k & x_{10^k}^{(1)} & x_{10^k} \\
1 & 15.0400117306 & 15.1346725729 \\
2 & 112.106568773 & 112.116435031 \\
3 & 1034.08180781 & 1034.08264064 \\
4 & 10102.9136866 & 10102.9137478 \\
5 & 100319.656432 & 100319.656436 \\
6 & 1001003.97574 & 1001003.97574 \\
\end{array}
\right)$$
Best Answer
If we go beyond for better accuracy, the logarithm in $$x_n^{(0)}=n+\sqrt n+\frac 14 \log(n)+\frac 12 \tag 1$$ is killing after Newton method.
Using instead $$x_n^{(0)}=n+\sqrt n$$ computing the first iterate of Householder method and expanding again as a series for large $n$. The result is (with $L=\log(n)$) $$x_n^{(1)}=n+\sqrt n+\frac L4 +\frac 12+$$ $$\frac{3 L^2+8 L+12}{32\, n^{1/2}}+\frac{2 L^3+6 L^2+15 L+12}{48\, n}+$$ $$\frac{125 L^4+400 L^3+1320 L^2+1728 L+1232}{6144\,n^{3/2}}+$$ $$\frac{81 L^5+270 L^4+1080 L^3+1800 L^2+2280 L+1120}{7680\, n^2}+$$ $$O\left(\frac{\log ^6(n)}{n^{5/2}}\right)$$ and we still have $g\big(x_n^{(1)} \big)$ postive.
Repeating the previous calculations
$$\left( \begin{array}{ccc} k & x_{10^k}^{(1)} & x_{10^k} \\ 1 & 15.0704798432 & 15.1346725729 \\ 2 & 112.114185500 & 112.116435031 \\ 3 & 1034.08259684 & 1034.08264064 \\ 4 & 10102.9137472 & 10102.9137478 \\ 5 & 100319.656436 & 100319.656436 \\ \end{array} \right)$$
Edit
In fact, we can avoid thinking about the first iterate of Newton-like method.
It is enough to write $$x=n+\sqrt n+\sum_{k=0}^p \frac {a_k} {n^{\frac k 2}}$$ Expanding $$g(x)=x\log(x)-(x+n)\log(x-n)$$ as a series for large $n$, cancelling one term at the time leads to the result (even if it starts to be tedious for $k>3$).
Edit
If you are interested by this problem, have a look here for @Roaman's, @user64494's and @Vaclav Kotesovec's contributions.
Using @Vaclav Kotesovec's formulae for $n=10$ $$\left( \begin{array}{cc} k & x_k \\ 1 & 14.6438158582 \\ 2 & 15.1069703071 \\ 3 & 15.1345865574 \\ 4 & 15.1346725720 \\ \end{array} \right)$$