Getting closer and closer

This is a complicated piece of convergence and error analysis. We shall do this in stages. First note that $-\ln(1-x) > x$ for all $0 < x < 1$ and also that $-\ln(1-x) < x + x^2$ for all $0 < x < \tfrac12$ .

We deduce from the above that $\big(1 - \tfrac{x}{n}\big)^{2n} \, \le \, e^{-2x}$ for all $0 < x < n$ , and that $\big(1 - \tfrac{x}{n}\big)^{2n} \, > \, e^{-2x - \frac{2x^2}{n}}$ for all $0 < x < \tfrac12n$ . Let us define $\alpha_{n,k} \; = \; \left\{ \begin{array}{ll} \tfrac{1}{k}\big(1 - \tfrac{k}{n}\big)^{2n} & 1 \le k \le n-1 \\ 0 & k \ge n \end{array} \right. \hspace{2cm} A \; = \; \sum_{k=1}^\infty \frac{e^{-2k}}{k} \; = \; \ln\left(\frac{e^2}{e^2-1}\right)$ Then we note that $0 \le \alpha_{n,k} \le \tfrac{e^{-2k}}{k} \hspace{1cm} k \ge 1\,,\,n \ge 2 \hspace{2cm} \lim_{n \to \infty} \alpha_{n,k} \; =\; \tfrac{e^{-2k}}{k} \hspace{0.5cm} k \ge 1$ Thus the Dominated Convergence Theorem tells us that $\lim_{n \to \infty} \sum_{k=1}^{n-1} \tfrac{1}{k}\big(1 - \tfrac{k}{n}\big)^{2n} \;= \; \lim_{n \to \infty} \sum_{k=1}^\infty \alpha_{n,k} \; = \; \sum_{k=1}^\infty \frac{e^{-2k}}{k} \; = \; A$ Since $3e^4(e^2-1) > 1000$ we note that $\begin{aligned} 0 \le A - \sum_{k=1}^{n-1} \tfrac{1}{k}\big(1 - \tfrac{k}{n}\big)^{2n} & = \sum_{k=1}^\infty \left(\frac{e^{-2k}}{k} - \alpha_{n,k}\right) \\ & \le \sum_{k=1}^2 \left(\frac{e^{-2k}}{k} - \alpha_{n,k}\right) + \sum_{k=3}^\infty \frac{e^{-2k}}{k} \\ & < \sum_{k=1}^2 \tfrac{1}{k}\big[e^{-2k} - \big(1 - \tfrac{k}{n}\big)^{2n}\big] + 10^{-3} \end{aligned}$ for all $n \ge 3$ . But then $\begin{aligned} 0 \le A - \sum_{k=1}^{n-1} \tfrac{1}{k}\big(1 - \tfrac{k}{n}\big)^{2n} & \le \sum_{k=1}^2 \tfrac{1}{k} e^{-2k}\big[1 - e^{-\frac{2k^2}{n}}\big] + 10^{-3} \\ & \le \sum_{k=1}^2 \frac{e^{-2k}}{k} \times \frac{2k^2}{n} + 10^{-3} \; = \; \frac{2}{n} \sum_{k=1}^2 ke^{-2k} + 10^{-3} \\ & < 2 \times 10^{-3} \end{aligned}$ using the Mean Value Theorem, provided that $n > 350$ .

We now define $\beta_{n,k} \; = \; \left\{ \begin{array}{ll} \tfrac{1}{k}\big(1 - \tfrac{k}{n}\big)^{n-1} & 1 \le k \le n-1 \\ 0 & k \ge n \end{array} \right. \hspace{2cm} B \; = \; \sum_{k=1}^\infty \frac{e^{-k}}{k} \; = \; \ln\left(\frac{e}{e-1}\right)$ Then we note that (we use the fact that $\tfrac{n}{k(n-k)} \le \tfrac{n}{n-1} < 2$ for $1 \le k \le n-1$ ) $0 \le \beta_{n,k} \le 2\tfrac{e^{-k}}{k} \hspace{1cm} k \ge 1\,,\,n \ge 2 \hspace{2cm} \lim_{n \to \infty} \beta_{n,k} \; =\; \tfrac{e^{-k}}{k} \hspace{0.5cm} k \ge 1$ Thus the Dominated Convergence Theorem tells us that $\lim_{n \to \infty} \sum_{k=1}^{n-1} \tfrac{1}{k}\big(1 - \tfrac{k}{n}\big)^{n-1} \;= \; \lim_{n \to \infty} \sum_{k=1}^\infty \beta_{n,k} \; = \; \sum_{k=1}^\infty \frac{e^{-k}}{k} \; = \; B$ Since $6e^5(e-1) > 1000$ , we have $\begin{aligned} \left|B - \sum_{k=1}^{n-1} \tfrac{1}{k}\big(1 - \tfrac{k}{n}\big)^{n-1}\right| & \le \sum_{k=1}^5 \tfrac{1}{k}\left| e^{-k} - \big(1 - \tfrac{k}{n}\big)^{n-1}\right| + \sum_{k=6}^\infty \frac{e^{-k}}{k} \\ & \le \sum_{k=1}^5 \frac{n}{k(n-k)}\left|\big(1 - \tfrac{k}{n}\big)e^{-k} - \big(1 - \tfrac{k}{n}\big)^n\right| + 10^{-3} \\ & \le \frac{2}{n}\sum_{k=1}^5 k e^{-k} + 2\sum_{k=1}^5 \left|e^{-k} - \big(1 - \tfrac{k}{n}\big)^n\right| + 10^{-3} \\ & \le \frac{2}{n}\sum_{k=1}^5 k e^{-k} + 2\sum_{k=1}^5 e^{-k}\left| 1 - e^{-\frac{k^2}{n}}\right| + 10^{-3} \\ & \le \frac{2}{n}\sum_{k=1}^5 k e^{-k} + 2\sum_{k=1}^5 e^{-k} \times \frac{k^2}{n} + 10^{-3} \\ & = \tfrac{2}{n} \sum_{k=1}^5 k(k+1)e^{-k} + 10^{-3} \end{aligned}$ for all $n > 10$ , using the Mean Value Theorem, from which we deduce that $\left|B - \sum_{k=1}^{n-1} \tfrac{1}{k}\big(1 - \tfrac{k}{n}\big)^{n-1}\right| \; \le \; 2 \times 10^{-3} \hspace{2cm} n \ge 5500$

Now for the problem itself. We have (note that the $k=n$ terms have to be handled separately) $\begin{aligned} f(a,n) & = \sum_{r=a-1}^{2a-1} \sum_{k=1}^n \frac{k^r}{n^{r+1}} \; = \; \frac{a+1}{n} + \sum_{r=a-1}^{2a-1} \sum_{k=1}^{n-1} \frac{k^r}{n^{r+1}} \\ & = \frac{a+1}{n} + \sum_{k=1}^{n-1} \frac{\frac{k^{a-1}}{n^a}\left(1 - \big(\frac{k}{n}\big)^{a+1}\right)}{1 - \frac{k}{n}} \\ & = \frac{a+1}{n} + \sum_{k=1}^{n-1}\frac{1}{n-k}\left(\big(\tfrac{k}{n}\big)^{a-1} - \big(\tfrac{k}{n}\big)^{2a}\right) \end{aligned}$ and hence $\begin{aligned} f(n,n) & = \frac{n+1}{n} + \sum_{k=1}^{n-1}\frac{1}{n-k}\left(\big(\tfrac{k}{n}\big)^{n-1} - \big(\tfrac{k}{n}\big)^{2n}\right) \\ & = \frac{n+1}{n} + \sum_{k=1}^{n-1} \frac{1}{k}\left[\big(1 - \tfrac{k}{n}\big)^{n-1} - \big(1 - \tfrac{k}{n}\big)^{2n}\right] \\ & = \frac{n+1}{n} + \sum_{k=1}^{n-1} \frac{1}{k}\big(1 - \tfrac{k}{n}\big)^{n-1} - \sum_{k=1}^{n-1} \frac{1}{k} \big(1 - \tfrac{k}{n}\big)^{2n} \end{aligned}$ and hence we have shown above that $\lim_{n \to \infty} f(n,n) \; = \; 1 + B - A \; = \; \ln(1+e) \; = \; 1.313261688$ Moreover $f(n,n)$ is within $5 \times 10^{-3}$ of this limit if $n > 5500$ . Certainly, then $f(10^7,10^7)$ is equal to $\boxed{1.3}$ to $1$ decimal place. Mathematica evaluates $f(10^7,10^7)$ as $1.31326$ to $5$ decimal places.