Tight upper bound on the sum of $\left( \frac{1}{k} \right)^k \exp \left(-\frac{\log(N)(\sqrt{N-k} - \sqrt{k})^2}{N}\right)$ Consider the following sum:
\begin{align}
      S = \sum_{k=\lceil\log(N)\rceil}^N\left(  \frac{1}{k} \right)^k \exp \left(-\frac{\log(N)(\sqrt{N-k} - \sqrt{k})^2}{N}\right).
\end{align}
Is it possible to show that this is sum is of order $1/N$ for  large $N$?
My attempt:
When $k$ is the same order as $N$, then $(1/k)^k$ is very small. It seems sufficient to consider $k \ll N$ and write
\begin{align*}
    S \leq N \frac{1}{(\log(N))^{\log(N)}} \exp( - \log(N)) \leq  \frac{1}{N},
\end{align*}
where I used the fact that $N \frac{1}{(\log(N))^{\log(N)}} \leq 1$ for $N$ large enough.
 A: You're absolutely right. Slightly more formally, we might do something like the following:
Expand out the exp term to get
$$
\sum k^{-k} \exp \left ( - \frac{\log N}{N} (N - 2 \sqrt{k(N-k)}) \right )
$$
Distributing and simplifying gives
$$
\sum k^{-k} \frac{1}{N} \exp \left ( \frac{2 \sqrt{k(N-k)} \log N}{N} \right )
$$
Then the stuff inside the $\exp$ is maximized when $k = \frac{N}{2}$. This is actually a terrible upper bound, but it's good enough for what we want. So our sum is at most
$$
\sum k^{-k} \frac{1}{N} e^{\log N}
$$
That is,
$$S_N \leq \sum_{k = \log N}^N k^{-k}$$
Now, as you've noticed, the first term will dominate this series. In fact, since we're already grossly overestimating from the last step, we might as well keep making our lives easy:
$$
\sum_{k = \log N}^N \left ( \frac{1}{k} \right )^k 
\leq 
\sum_{k = \log N}^\infty \left ( \frac{1}{\log N} \right )^k
$$
But now we're in the clear! Applying the formula for a geometric series gives
$$
S_N \leq 
\left ( \frac{1}{\log N} \right )^{\log N} \frac{1}{1 - \frac{1}{\log N}}
$$
Of course, $\frac{1}{1 - (\log N)^{-1}} \leq 2$ for $N > 8$ or so, which means we can safely ignore it. So at long last
$$
S_N \leq O  \left ( \left ( \frac{1}{\log N} \right )^{\log N} \right ).
$$
This is actually better than $O \left ( \frac{1}{N} \right )$, even if it's not obvious at first. You can compute
$\lim_{n \to \infty} \frac{(\log N)^{-\log N}}{N^{-1}} = 0$ (or look at a graph) to convince yourself of this.

I hope this helps ^_^
