Estimate a sum of fractions Are there any easy ways to prove that:
$$
\sum_{j=1}^{k-1} \left({j \over k - j}\right)^{k - 2j - 1} = O(\sqrt k)
$$
or give some other estimates to the sum.
 A: This is not a math proof - just some heuristic considerations.
We can observe first that terms of the sum decline very rapidly at $j\to1$ and $\to{k}$ (at the beginning and the end of the sum)- as $\sim\left(\frac{1}{k}\right)^{\sim{k}}$. In the "middle" of the sum (at $j\to\frac{k}{2}$) they have a "maximum" $\sim\left(\frac{k}{k}\right)^{\sim0}\sim1$, so we may conclude that main contribution comes from this "middle" part of the sum.
Having said that we change the order of summation and consider $j=\frac{k-1}{2}+l$, where l goes from some negative number through zero to some positive number.
We may suppose that $l<<k$ (at $l\sim{k}$ terms are small), but $l$ may be $>>1$ and $l^2$ may be $>>k$
At $k-j=\frac{k+1}{2}-l$ and $k-1-2j=-2l$
we get
$S(k)\sim\sum_l \left(\frac{\frac{k-1}{2}+l}{\frac{k+1}{2}-l}\right)^{-2l}=\sum_l \left(\frac{\frac{2l-1}{k}+1}{\frac{1-2l}{k}+1}\right)^{-2l}$$\sim\sum_l \left(1-\frac{2}{k}+\frac{4l}{k}\right)^{-2l}=\sum_l e^{-2l\ln(1-\frac{2}{k}+\frac{4l}{k})}\sim\sum_l e^{-2l(-\frac{2}{k}+\frac{4l}{k})}=\sum_l e^{-\frac{8l^2}{k}+\frac{4l}{k}}$.
Basically, with our calculation accuracy we don't need to keep $\frac{4l}{k}$ in the power of the exponent - we will see that it won't contribute into the main asymptotics term.
$S(k)\sim\sum_l e^{-\frac{8l^2}{k}+\frac{4l}{k}}\to\int_{-\infty}^{\infty}e^{-\frac{8l^2}{k}+\frac{4l}{k}}dl=\int_{-\infty}^{\infty}e^{-\frac{8}{k}(l-\frac{1}{4})^2}\exp({\frac{1}{2k}})dl=\sqrt{\frac{\pi{k}}{8}}\exp(\frac{1}{2k})\sim\sqrt{\frac{\pi{k}}{8}}$
Supplement
If we want to get a better approximation we have to dig a bit deeper.
We can easily show that the initial sum is equal to $S(k)=S_1(k)+S_2(k)=\sum_{l=0}^{\frac{k-3}{2}}(\frac{k-1-2l}{k+1+2l})^{2l}+\sum_{l=1}^{\frac{k-1}{2}}(\frac{k+1-2l}{k-1+2l})^{2l}$. Making change in the first sum ($l\to-l$) we get $$S(k)=\sum_{l=-\frac{k-3}{2}}^{\frac{k-1}{2}}(\frac{k+1-2l}{k-1+2l})^{2l}=\sum_{l=-\frac{k-3}{2}}^{\frac{k-1}{2}}e^{2l\log\frac{k+1-2l}{k-1+2l}}$$
We are looking for the asymptotics in powers of $k$, and because the terms of the sum decrease very rapidly at $l\to\frac{k-1}{2}$ and $l\to-\frac{k-3}{2}$ (as $\sim{k}^{-k}$) we can expand the summation to +-$\infty$. Next, we want to replace summation with integration by means of Euler-Maclaurin formula $\sum_a^b{f}(l)\sim\int_a^bf(l)dl+\frac{1}{2}(f(a)+f(b))+\frac{1}{12}(f^{(1)}(b)-f^{(1)}(a))+..  $.  But we easily see that all correction terms should be calculated on the boundaries of summation, where $f(\frac{k}{2})\sim{f^{(p)}}(\frac{k}{2})\sim{k}^{p}{k}^{-k}$ and, therefore, can be omitted.
So, to obtain the asymptotic correction terms we should only deal with logarithm:
$S(k)\sim\int_{-\infty}^{\infty}e^{2l\log\frac{k+1-2l}{k-1+2l}}dl=\frac{1}{2}\int_{-\infty}^{\infty}{e}^{l\left(\frac{1}{k}-\frac{l}{k}-\frac{(1-l)^2}{2k^2}+\frac{(1-l)^3}{3k^3}-...+\frac{1}{k}-\frac{l}{k}+\frac{(1-l)^2}{2k^2}+\frac{(1-l)^3}{3k^3}+...\right)}dl$
If we want to obtain the first asymptotic correction term ($\sim\frac{1}{\sqrt{k}}$) we don't need to keep in the power of exponent the terms with power of order $\frac{l^6}{k^5}$ or higher - they will only contribute into correction terms of order $\sim\frac{1}{k\sqrt{k}}$.
We get (keeping only the terms of order $\sim\sqrt{k}$ and $\sim\frac{1}{\sqrt{k}}$):
$S(k)\sim\frac{1}{2}\int_{-\infty}^{\infty}{e}^{l\left(\frac{2}{k}-\frac{2l}{k}+\frac{2}{3}\frac{(1-l)^3}{k^3}\right)}dl=\frac{1}{2}e^{\frac{1}{2k}}\int_{-\infty}^{\infty}{e}^{-\frac{2}{k}(l+\frac{1}{2})^2+\frac{2}{3}\frac{l(1-l)^3}{k^3}}dl$$\sim\frac{1}{2}e^{\frac{1}{2k}}\int_{-\infty}^{\infty}{e}^{-\frac{2}{k}t^2}\left(1+\frac{2}{3}\frac{(t-\frac{1}{2})(\frac{1}{2}-t)^3}{k^3}\right)dt\sim\frac{1}{2}e^{\frac{1}{2k}}\int_{-\infty}^{\infty}{e}^{-\frac{2}{k}t^2}\left(1-\frac{2}{3}\frac{t^4}{k^3}\right)dt$
Finally we have
$$S(k)\sim\sqrt{\frac{\pi{k}}{8}}\left(1+\frac{3}{8k}+O(\frac{1}{k^2})\right)$$
Asymptotics of higher order can be easily obtained in the same way.
Some figures

