What strategies can I use to evaluate a limit when Limit[] returns unevaluated

Question

I'm trying to find the following limit using Mathematica:

$$\lim_{N\to\infty}\sum_{k=1}^N\left(\frac{k-1}{N}\right)^N$$

The problem is taken from here and is known to converge to $\displaystyle\frac{1}{e-1}$. However, using Limit in a straightforward manner returns unevaluated:

Limit[Sum[((k - 1)/n)^n, {k, 1, n}], n -> ∞]
(* Limit[Sum[((k - 1)/n)^n, {k, 1, n}], n -> ∞] *)

How can I explore this problem using Mathematica and obtain the limit?

Answer 1

Identifying the sum as ($N$ times) a Riemann sum should inspire us to look at the integral of the function $x^N$ for $0\le x \lt 1$, whose value is $1/(N+1)$, of which here are a few examples for $N=1,4,16,64$:

Plot[Evaluate@Table[x^n, {n, {1, 4, 16, 64}}], {x, 0, 1}, Filling -> Axis,  PlotStyle -> Thick]

Noticing that this area becomes more and more concentrated near $x \approx 1$, we should then suspect that virtually all of the sum's value is coming from the last few terms. Why not, then, use Mathematica to explore this?

Table[Limit[Sum[((k - 1)/n)^n, {k, n - i, n}], n -> \[Infinity]], {i, 0, 4}]

$\left\{\frac{1}{e},\frac{1+e}{e^2},\frac{1+e+e^2}{e^3},\frac{1+e+e^2+e^3}{e^4},\frac{1+e+e^2+e^3+e^4}{e^5}\right\}$

The pattern is clear. Mathematica will identify it:

FindSequenceFunction[%][i]

$\frac{e^{-i} \left(e^i-1\right)}{e-1}$

That is, we can speculate from this evidence that

$$\lim_{n\to \infty } \, \sum_{k=n-i}^n\left(\frac{k-1}{n}\right)^n = \frac{e^{-i} \left(e^i-1\right)}{e-1}.$$

It looks good when we compare the sums to the limiting value of the right hand side, easily seen (or computed by Mathematica) to be $1/(e-1)\approx 0.581977$:

DiscretePlot[1/(E-1) - Sum[((k-1)/n)^n, {k, 1, n}], {n, 10, 1000, 20}, PlotStyle -> PointSize[0.015]]

If we can mathematically justify taking the double limit--first with respect to $n$, then with respect to $i$--then we can conclude the right hand side converges to $1/(e-1)$. I leave that reasoning to the interested reader.