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)$

Question

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.

Answer 1

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 ^_^