What is the general formula for power series summation?

Question

While reviewing definite integrals, $\int_a^bf(x)dx$; I recalled that a definite integral could not only be solved by the difference of the anti-derivatives of intervals b and a, $F(b)-F(a)$, via the 2nd fundamental theorem of calculus, but also through the Riemann summation: $$\lim_{n\to\infty}f(x_i^*)\Delta x;\ \textrm{where}\ \Delta x=\frac{b-a}{n}\ \textrm{and}\ x_i^*=a+(\Delta x)i$$ Given this, I tried out an integral over an example polynomial. The difference of anti-derivatives would've given a sufficient answer, but I wanted to try it with Riemann sums. While attempting to solve this example, I came across sums of the form $\sum_{i=1}^ni^k$. Thankfully, I recalled the formulas for $k=\{1,2,3\}$ which were as follows: $$\sum_{i=1}^ni^1=\frac{n\cdot(n+1)}{2}$$ $$\sum_{i=1}^ni^2=\frac{n\cdot(n+1)\cdot(2n+1)}{6}$$ $$\sum_{i=1}^ni^3=\frac{n^2\cdot(n+1)^2}{4}$$ This allowed me to solve the problem, however I wondered about orders of k greater than 3. What is the general formula for $\sum_{i=1}^ni^k$ given any value of k and how would I prove it?

Answer 1

Monomials play nicely with integrals, but not so nice with summations. Better to ask: How to calculate the sum $\sum_{i=0}^n {i\choose k} = \frac{1}{k!}\sum_{i=0}^n i(i-1)\cdots (i-k+1)$?

Now this is a combinatorics question: $\sum_{i=0}^n {i\choose k} = {{n+1}\choose{k+1}}$, which is sometimes called the hockey stick identity. In any case, it can be proved by counting the number of ways of choosing $k+1$ elements from the set $\{1,2,\ldots n+1\}$, where the largest element we choose is $i+1$.

This lets us quickly find, for example, $\sum_{i=0}^n i^2$. We have $i^2 = 2{i\choose 2} + {i\choose 1}$, so $\sum_{i=0}^n i^2 = 2 \sum_{i=0}^n {i\choose 2} + \sum_{i=0}^n {i\choose 1} = 2{{n+1}\choose 3} + {{n+1} \choose 2} = \frac{(n+1)n(n-1)}{3} + \frac{(n+1)n}{2} = \frac{n(n+1)(2n+1)}{6}$.

---

If you want a general formula for $\sum_{i=1}^n i^k$, then combine the above with some careful combinatorics regarding the coefficients of $i(i-1)\cdots (i-k+1)$. I have never really liked this approach, since I feel that Stirling/Bernoulli numbers overcomplicate matters; you get similar results if you ask for a closed form of the integral $\int {x\choose k}dx$.

Answer 2

Consider the function:

$$f(x) = \sum_{k=0}^{n}\exp(-k x)$$

This is a geometric series, so you can easily calculate $f(x)$ in the closed form. Expanding both sides in powers of $x$ will yield the desired summations.