Hint on power sum coefficients

Question

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 04: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 04: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 04:29
@CalvinLin Wow, that's a pretty amazing fact I didn't know about. Do have any reference where I can read about it? — Pratyush Sarkar, Sep 28 '13 at 04:30
@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 04:34
Hm yes, you should be able to substitute in a positive integer. Well then, here's another. What is $P(-1)$, the alternating sum of the coefficients? — Calvin Lin, Sep 28 '13 at 04:52
@CalvinLin, I haven't found a way to get the alternating sum yet, but I haven't given up. However, I've calculated $a_{k+1}$, $a_k$, and $a_{k-1}$, and I'm wondering if you know if I'm likely to see a pattern if I do more of these calculations—they get longer and longer as $j$ decreases, so if there's nothing to see there, I'll try to come at it from a different direction. — dfeuer, Sep 28 '13 at 21:20
That said, I'm already starting to wonder whether a previous form I found has something to offer from the linear algebra side of things—I'm a bit rusty on Cramer's rule and such, but I think there may be something down that road. — dfeuer, Sep 28 '13 at 21:33
As a hint to the alternating sum, show that $x+1 | P(x)$, hence conclude that the value of $P(-1)$ is ... Re pattern of $a_j$, as I said, I'd be amazed if you can find the pattern. — Calvin Lin, Sep 28 '13 at 21:43
@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 01:08

score 2 · Answer 1 · answered Sep 29 '13 at 20:38

2

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.

answered Sep 29 '13 at 20:38

Marc van Leeuwen

115,048

What does $\binom i k$ mean when $i<k$? – dfeuer Sep 29 '13 at 21:03
1

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 06:25

score 0 · Answer 2 · answered Sep 28 '13 at 04:42

0

Look at the Riemann and Hurwitz zeta functions.

answered Sep 28 '13 at 04:42

Betty Mock

3,532

Gottfried Helms · Answer 3 · 2013-09-29T20:28:38.173

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

Hint on power sum coefficients

3 Answers3