Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please do not give anything more than a tiny hint for this question.

I know that there is a well-known formula for $$\sum_{i=1}^n i^k,$$ where $k$ is any non-negative integer. I have been able to prove that in fact it is a polynomial in $n$, $$\sum_{i=1}^n i^k = \sum_{j=0}^{k+1} a_j n^j,$$ with high-order term $\frac 1 {k+1} n^{k+1}$ and zero constant term. In the process, I found a rather awkward method of calculating the rest of the coefficients. I'm now trying to figure out what the rest of them are. So far, I've gotten $$a_j = \frac{k!}{j!(k-j+1)!}-\sum_{m=j+1}^{k+1}a_{m}\frac{m!}{j!(m-j+1)!},$$ where $a_j$ is the coefficient of $n^j$ (for $j\le k$). Can someone give me a tiny hint on how to proceed? Please do not go and tell me what the coefficients are, or how the rest of the proof goes, or anything like that.

share|cite|improve this question
Since you specifically said not to say what the coefficients are etc, I will just make a small comment here. These coefficients are complicated and its very hard to get a explicit formula. Bernoulli was able to get an expression for it and it is closely related to Bernoulli numbers. – Pratyush Sarkar Sep 28 '13 at 4:24
Agreed. I would be amazed if you can guess the formula by just staring at a few initial values. Something related that you can work on, is to show that the sum of coefficients is 1. – Calvin Lin Sep 28 '13 at 4:27
@PratyushSarkar: unfortunately, the Wikipedia article on Bernoulli numbers seems (based on the links on top) to have more information about this problem than I want to see just yet... – dfeuer Sep 28 '13 at 4:29
@CalvinLin, that's entirely trivial, no? Setting $n=1$ in $\sum_{i=1}^n i^k = \sum_{m=0}^{k+1} a_m n^m$ gives that immediately, right? – dfeuer Sep 28 '13 at 4:34
@hmedan.mnsh, I don't have a link, no, but if you set up a proof by induction on $n$ as though you knew what the coefficients are, you will always be able to choose a high-order coefficient, and then the next one down, etc., so that the inductive step will work regardless of the value of $n$. As for getting drop of intuition to start, the fact that $\int_0^n x^k\,dx = n^{k+1}/(k+1)$ is certainly very suggestive. I really wish I knew a way to refine that integral approximation to get more coefficients. – dfeuer Sep 29 '13 at 1:08

One hint is that it is far easier to do this is you replace $i^k$ by another polynomial of degree $k$ in $i$, namely by$~\binom ik$. Check that you can find $\sum_{i=0}^n\binom ik$ easily. Then it is theoretically only a question of transforming the basis $[1,i,i^2,\ldots]$ of the polynomial functions in$~i$ to the basis $[\binom i0=1,\binom i1=i,\binom i2=\frac{i(i-1)}2,\ldots]$ and back. In practice this messes the concrete values up considerably.

share|cite|improve this answer
What does $\binom i k$ mean when $i<k$? – dfeuer Sep 29 '13 at 21:03
It still means $\frac{i(i-1)(i-2)\ldots(i-k+1)}{k!}$. If $i$ is integer and $0\leq i<k$ then this is $0$ because of a factor $i-i=0$ in the numerator. – Marc van Leeuwen Sep 30 '13 at 6:25

Look at the Riemann and Hurwitz zeta functions.

share|cite|improve this answer

Please take this not yet as an answer, only it is too long for the comment-box

Hmm, I thought to help, but I'm not sure that I understand your question at all. If I read your equation correctly, then a coeffcient $a_j$ is explained by the higher ones $a_{j+1}, a_{j+2} ,... a_{k+1}$. So this ( for a certain $k$ ) looks like a matrix equation of the following type $ C*A=A$ where $C$ contains your binomial-coefficients: $$ \begin{array}{lll} \begin{array}{lll} \end{array}& *&\begin{bmatrix} 1\\ a_1\\a_2\\a_3\\a_4\\a_5 \end{bmatrix} \\ \begin{bmatrix} c_{1,0}&.&c_{1,2}&c_{1,3}&c_{1,4}&c_{1,5}\\ c_{2,0}&.&. & c_{2,3}& c_{2,4}& c_{2,5}\\ c_{3,0}&.&. &. &c_{3,4}&c_{3,5}\\ .&.&. &. & 1 & .\\ .&.&. &. & .& 1\\ \end{bmatrix}& =&\begin{bmatrix} a_1\\a_2\\a_3\\a_4\\a_5\\ \end{bmatrix} \\ \end{array}$$ but where for instance $a_4$ and $a_5$ are given(?) and are inserted in the upper vector $A$ (and then "computed" into the lower vector $A$). The iteration begins then that with them and your given coefficents $c_{j,m}$ from there $a_3$ is computed in the lower $A$-vector (and then also inserted in the upper $A$-vector) and then $a_2$ and finally $a_1$.

So for instance , your equation $$a_j = \frac{k!}{j!(k-j+1)!}-\sum_{m=j+1}^{k+1}a_{m}\frac{m!}{j!(m-j+1)!}$$ for j=3 and k+1=5 becomes $$a_3 = \frac{4!}{3!2!}-(a_4\frac{4!}{3!(2)!} + a_5\frac{5!}{3!(3)!}) $$ and this is expressed in the matrix-form by the third row where we get $$ a_3 = c_{3,0}+ a_4 c_{3,4} + a_5 c_{3,5} $$ (only where I have made the minus-signs in the coefficients $c_{j,m}$ to make the appearance clearer) and then $a_2$ can be computed by the second row of the matrix-schema: $$ a_2 = c_{2,0}+ a_3 c_{2,3}+ a_4 c_{2,4} + a_5 c_{2,5} $$

Is that correct so far?
(The first idea would then be that this can be handled as an eigenvalue/eigenvector -problem of the matrix $C$ )

share|cite|improve this answer
I don't really understand what you're doing there. There definitely does seem to be something very triangular about the equation I found, and you seem to be doing something with that, but I don't quite see what. – dfeuer Sep 29 '13 at 20:14
@dfeuer - I'll put an explanation into the answerbox – Gottfried Helms Sep 29 '13 at 20:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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