Today I was thinking about the value of the sum $S(n,d) = \sum_{k=1}^n k^d$ as $n$ gets large. I suspected the solution would be $S(n,d) \approx \frac{n^{d+1}}{(d+1)}$ based on looking at the cases $d = 1$ and $d=2$, but it was not initially obvious as to how I might prove it. Assuming $n$ gets large so some terms can be simplified, the approach I took was the following:
\begin{align} S(n,d) &= \sum_{k=1}^n k^d \\ &= \frac{n^{d+1}}{n-1} \sum_{k=1}^n \left(\frac{k}{n}\right)^d \frac{n-1}{n}\\ &\approx n^{d} \int_{1}^{n} \left(\frac{x}{n}\right)^d dx \\ &\approx n^{d} \left( \frac{n}{d+1}\left(\frac{x}{n}\right)^{d+1}\right]_{1}^{n} \\ &\approx \frac{n^{d+1}}{d+1} \left( 1 - \frac{1}{n^{d+1}}\right) \\ &\approx \frac{n^{d+1}}{d+1} \end{align}
My question is, what is some other approach I could take that would avoid integration?
Sketch:
A $(d+1)$-dimensional hypercube with sides of length $n$ can be divided into $d+1$ congruent hyperpyramids with bases that are $d$-dimensional hypercubes. (See here for some pictures of the 3D case and a proof.)
Taking one of these hyperpyramids, we can slice it, parallel to the base, into $n$ $d$-dimensional objects, basically $d$-hypercubes with height $1$ and chamfered edges.
We can approximate each of these objects by $d$-hypercube-slabs of height $1$ and other sides $k$. Now, the crucial bit: what is the error in making this approximation? At the end of the day, what we care about is that the error occurs along the edge, to at most a finite, uniform depth. Hence the error in one is approximately the hyperarea of the edge of a hypercube, i.e. $O(k^{d-1})$. Adding up the errors gives (and here we'll cheat and use induction) a total error of $O(n^d)$. Hence $$ (d+1) \sum_{k=1}^n k^d = n^{d+1} + O(n^d). $$