# Hint on power sum coefficients

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.

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

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

-

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

-
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