1
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by ccorn, JimmyK4542, Micah, user147263, Moishe Kohan Oct 13 '14 at 22:11

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ It's from the defition of the generalized harmonic number. You may not get the answer you expected as it comes from manipulating a defition instead of deriving it. $\endgroup$ – UserX Oct 13 '14 at 21:14
  • $\begingroup$ @UserX Wouldn't the definition of the generalized harmonic number be $H_n^{(-k)}=\sum_{i=1}^n\frac{1}{i^{(-k)}}=\sum_{i=1}^ni^k;\ n\in\mathbb{N}$? $\endgroup$ – Anthony Vanover Oct 13 '14 at 21:22
  • $\begingroup$ @Antonius yes that's the one I'm talking about. $\endgroup$ – UserX Oct 13 '14 at 22:01
3
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.