I was inspired by considering the following:

$$\left(\sum_{i=1}^n i\right)^2=\sum_{i=1}^n i^3$$

Are there exact formulas for the sums of the powers of the integers? For example, we have:

$$\sum_{i=1}^n i={n(n+1)\over 2}$$

$$\sum_{i=1}^n i^2={n(n+1)(2n+1)\over 6}$$

Do we have more of these? Then I began to consider them using binomial notation:

$$\sum_{i=1}^n i={n(n+1)\over 2}={n+1\choose 2}$$

$$\sum_{i=1}^n i^2={n(n+1)(2n+1)\over 6}={n+1\choose 3}+{n\choose 3}$$

Upon further searching, I managed to come up with the following:

$$\sum_{i=1}^n i^3={n+2\choose 4}+4{n+1\choose 4}+{n\choose 4}={n+1\choose 2}^2$$

$$\sum_{i=1}^n i^4={n+3\choose 5}+11{n+2\choose 5}+11{n+1\choose 5}+{n\choose 5}$$

$$\sum_{i=1}^n i^5={n+4\choose 6}+26{n+3\choose 6}+66{n+2\choose 6}+26{n+1\choose 6}+{n\choose 6}$$

I know that these could also be written in terms of decreasing choice (i.e., $a{n\choose 5}+b{n\choose 4}+c{n\choose 3}+\dots$), but I wonder about the particular coefficients displayed here. Note that these coefficients are the same ones that would be used if the formula were to generate the sequence of "powers of n" instead of the sum over them due to the identity ${n+1\choose k+1}-{n\choose k+1}={n\choose k}$. I have found a recursive formula for them given exponent $k$:

$$a_k(i)=i^k-\sum_{j=1}^{i-1}a_k(j){k+i-j\choose k}$$

The first few sequences are:

1 = 1!
1 1 = 2!
1 4 1 = 3!
1 11 11 1 = 4!
1 26 66 26 1 = 5!

So my questions are:

  • Does the sequence of coefficients for a given $k$ have a name? I see that for each $k$ the sum over the sequence is $k!$. Note that the Bernoulli numbers are not the same as these since these are constructed individually for each $k$, and for all $i\gt k, a_k(i)=0$.
  • These sequences are symmetrical and appear to have properties very similar to that of Pascal's Triangle. Is there a simple rule to generate them along the same lines?
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Faulhaber%27s_formula $\endgroup$ – martini Oct 8 '13 at 14:36
  • $\begingroup$ @martini: perfect, exactly what I was looking for. Although the article is short on details about the sequence of coefficients... Have I reconstructed the Bernoulli numbers? I thought they always summed to zero... $\endgroup$ – abiessu Oct 8 '13 at 14:52

Using $\def\falling#1{^{\underline#1}}x\falling k=k!\binom xk=x(x-1)\ldots(x-k+1)$ (also written as $(x)_k$, but I find is unpleasant to read), one has $$ \def\stirs{\genfrac\{\}0{}}x^n=\sum_{k=0}^n \stirs nk x\falling k, \qquad\text{and hence}\quad x^n=\sum_{k=0}^n k!\stirs nk \binom xk $$ where $\stirs nk$ denote the Stirling numbers of the second kind. The inverse transformation uses (signed) Stirling numbers of the first kind $\def\stirf{\genfrac[]0{}}(-1)^k\stirf nk$: $$ x\falling k=\sum_{k=0}^n (-1)^k\stirf nk x^k \qquad\text{and hence}\quad \binom nk=\sum_{k=0}^n \frac{(-1)^k}{k!}\stirf nk x^k. $$ These numbers have many interesting combinatorial properties, but no simple closed formula.

Your question seems to pursue another course, the numbers $a_k(i)$ appear to be the Eulerian numbers $\genfrac<>0{}ki$.

| cite | improve this answer | |
  • $\begingroup$ Just to clarify, are you saying that my sequence numbers $a_k(i)$ are equivalent to $i!\stirs ki$? I am not suggesting that my recursive formula is correct, but that the sequence of coefficients that I have labeled $a_k(i)$ should match the values $i!\stirs ki$... $\endgroup$ – abiessu Oct 8 '13 at 15:41
  • $\begingroup$ No, clearly those numbers $a_k(i)$ fail to be divisible by $i!$ in general (the Stirling numbers are integers). See my addition; they are (very probably) Eulerian numbers. $\endgroup$ – Marc van Leeuwen Oct 8 '13 at 15:45
  • $\begingroup$ Got it! That's the exact set of sequences. Thank you! $\endgroup$ – abiessu Oct 8 '13 at 15:52

Have a look at $\sum_{i=1}^{n}i\left(i-1\right)\cdots\left(i-k+1\right)$. They are easier to deal with and the $\sum_{i=1}^{n}i^{k}$ can be deduced from them. It becomes something like $\left(n+1\right)n\cdots\left(n-k+1\right)$ preceded by a constant and it can easily be verified with induction.

| cite | improve this answer | |
  • $\begingroup$ It would seem that $\sum_{i=k}^{n}i\left(i-1\right)\cdots\left(i-k+1\right)$ has a more appropriate starting point... Are you directly writing out the $(i)_k$ Pochhammer symbol in that sum? $\endgroup$ – abiessu Oct 8 '13 at 14:49
  • $\begingroup$ Note that $i(i-1)\ldots(i-k+1)=k!\binom ik$ so this approach is up to constant factors (that only depend on the degree) the same as the one mentioned in the question. $\endgroup$ – Marc van Leeuwen Oct 8 '13 at 15:00
  • $\begingroup$ Yes that is a shorter notation for it. $\endgroup$ – drhab Oct 8 '13 at 15:00
  • $\begingroup$ @drhab: I appreciate the offer of an alternate approach, but I have found that when I use binomial terms I often have fewer extra constants to deal with overall, and I have the added bonus of the identity mentioned in the question. $\endgroup$ – abiessu Oct 8 '13 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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