Deriving the summation formula for $x^2, x^3,\ldots,x^n$ How is the summation formula's for $x,x^2,x^3,x^4,\ldots$ derived? I know how to do it for $x$ which is $n^2/2 + n/2$ but I am having hard time deriving the summation formula for $x^n$ on my own. I heard the best way to do it was by binomial coefficient but I don't see it. Before posting, I read couple of posts but none helped. So if you know and direct me towards any post or a webpage (wiki) that can help, that would be great. If not, any input would be much appreciated.
 A: I can show you by the example of $x^2$, and I hope that you can see how to generalize the method. Begin with:
$$\displaystyle\sum\limits_{i=1}^n i^2 = \int_0^n\!x^2 dx\ + \zeta(n)$$
With this, a simple integral can be carried out, and the only work left to do is to determine $\zeta(n)$, the error resulting from using an integral approximation.

To do so, consider the figure shown above, a snippet of the $y=x^2$ curve.  The shaded region represents the area not captured in the integral and thus is the error.  Any particular area of shading, $A$, for example the area from $x=1$ to $x=2$, can be represented with this: 
$$
A(a) = \int\limits_{a^2}^{(a+1)^2} \int\limits_{a}^{sqrt(y)}1\,dxdy = \int\limits_{a^2}^{(a+1)^2}sqrt(y) - a \,dy
$$
And this simplifies nicely to:
$$
A(a) = a + \frac{2}{3}
$$
Now, we add these up to determine the total error:
$$ \zeta(n)\ = \displaystyle\sum\limits_{a=0}^{n-1} a+\frac{2}{3}\ = \displaystyle\sum\limits_{a=1}^n a-1+ \frac{2n}{3} $$
Finally,
$$\zeta(n)\ = \frac{n(n+1)}{2}\ - \frac{n}{3}$$
Then, the total summation results from adding this result to the first integral.
$$\displaystyle\sum\limits_{i=1}^{n}i^2\ = \frac{n^3}{3} + \frac{n(n+1)}{2}\ - \frac{n}{3} = \frac{n(n+1)(2n+1)}{6} $$ 
A: For the sum of $x^2$, I hope this The sum of the squares of the first n natural numbers could be helpful. Actually, you can follow the same method for $x^n$.
A: For the general solution, the easiest path is to use the Euler-Maclaurin formula to compute the sum:
$$
S_m(n) = \sum_{0 \le k \le n - 1} k^m
$$
as:
$$
 S_m(n)
      = \frac{1}{m + 1} \,
          \left(
            \sum_{0 \le k \le m}
              \binom{m + 1}{k} \, B_k n^{m + 1 - k}
          \right)
$$
Here $B_k$ are the Bernoulli numbers
A: One way to do is is to define falling factorial powers as:
$$
x^{\underline{m}} = x (x - 1) \ldots (x - m + 1)
$$
It is easy to prove by induction that:
$$
\sum_{1 \le k \le n} k^{\underline{m}} = \frac{n^{\underline{m + 1}}}{m + 1}
$$
There is one way to express $x^m$ as a combination of falling factorial powers, given by Stirling numbers of the second kind:
$$
x^m = \sum_{0 \le k \le m} \genfrac{\{}{\}}{0pt}{}{m}{k} x^{\underline{k}}
$$
(or you can just set up the relevant equations, they are easy to solve by hand for any particular $m$). The result is then easy:
$$
\sum_{1 \le k \le n} k^m
  = \sum_{1 \le r \le m} \frac{1}{r + 1} \genfrac{\{}{\}}{0pt}{}{m}{r} n^{\underline{r + 1}}
$$
This is convenient for calculation for smallish $m$.
A: Here's a brainless approach: When summing $x^k$, you expect a polynomial of order $x^{k+1}$. There are a number of fuzzy reasons why this is the case, e.g. because integration is similar to summing, cf. michael10000's answer.
In any case, a polynomial of order $n$ is determined by its values at $n + 1$ points, and it's easy to calculate the first $n + 1$ values of this polynomial, so you can just use any number of methods for polynomial interpolation (I wrote an article leading you through one method: Interpolating Polynomials) to work out what all the coefficients are.
