Are there any easy methods of estimating an explicit formula for $\sum_{i=1}^n i^\left(i+1\right)$?

Question

I believe the title is pretty clear on what I'm asking for. I guess the part about "easy methods" might be ambiguous. What I mean by "easy methods" is: methods which does not (necessarily) require more than basic one variable calculus.

Answer 1

If you are OK with approximate solution, we can start by approximating the sum

$$S(N) = \sum_{k=1}^N k^k$$ by simply skipping all but the latest term. If we plot the relative errors we get $$e(N) = \frac{1+2^2+\cdots+ N^N}{N^N}$$

We fit this $e(N)$ to a reciprocal polynomial model of order 4:

$$P(N) = \sum_{k=0}^{4}\frac{c_k}{N^k}$$

(Using least squares fit which you will learn in a first linear algebra course)

Gives a pretty good fit up to $N=64$:

Maybe you can use this observation to build your own even better estimator?

Answer 2

As @mathreadler noted, we can approximate this sum of fast-growing terms with the last term. Obviously, the sum's true value is greater (if $n\ge2$), but what's the relative error? Numerical experiments suggest $\frac{1}{en}$, i.e.$$\sum_{i=1}^{n-1}i^{i+1}\approx\frac{n^n}{e}.$$Indeed, incrementing $n$ increases the left-hand side by $n^{n+1}$, and the latter by$$\frac{(n+1)^{n+1}-n^n}{e}\approx\frac{n^n}{e}\cdot\left((n+1)\left(1+\frac1n\right)^n-1\right)\approx n^{n+1}.$$