# Cant spot the pattern!

1. Nov 16, 2005

I am supposed to derive a conjecture for the series:

1^k + 2^k + 3^k +...+n^k

I know and have proved that the following are valid:

sum of n^1 = (1/2)(n^2 + n)

sum of n^2 = (1/6) (2n^3 + 3n^2 + n)

Sum of n^3 = (1/4)(n^4 +2n^3 + n^2)

sum of n^4 = (1/30) (6n^5 + 15n^4 + 10n^3 - n)

Anyone spot any patterns? I cant!

2. Nov 16, 2005

### benorin

You can use polynomial curve fitting (eqivalent to using Lagrange Interpolating Polynomials) to solve it:

Recall that there is precisely one polynomial of degree n that passes through n+1 distinct points. It's simple in concept, but the formula is somewhat ugly, where: Suppose you are given three points, say

$$\left( x_{1}, y_{1}\right) ,\mbox{ } \left( x_{2}, y_{2}\right) ,\mbox{ and } \left( x_{3}, y_{3}\right)$$

then the polynomial that interpolates (that is fits) those points is of degree 3-1=2, and will consist of three terms. It is

$$P(x) = y_{1}\frac{\left( x-x_{2}\right) \left( x-x_{3}\right) }{\left( x_{1}-x_{2}\right) \left( x_{1}-x_{3}\right)} + y_{2}\frac{\left( x-x_{1}\right) \left( x-x_{3}\right) }{\left( x_{2}-x_{1}\right) \left( x_{2}-x_{3}\right)} + y_{3}\frac{\left( x-x_{1}\right) \left( x-x_{2}\right) }{\left( x_{3}-x_{1}\right) \left( x_{3}-x_{2}\right)}$$

since we wanted it to have the value $$y_{1}$$ at $$x_{1}$$, the first term does this and it is zero at $$x_{2}\mbox{ and } x_{3}$$ (this is the numerator) and the denominator ensures that at $$x_{1}$$ the numerator terms are corrected for so that it is still $$y_{1}$$ there. The other terms likewise.

To sum the k-th powers of the first n integers first note that the sum is a polynomial in n of degree k+1 (you have proved this for k=1,...,5 already), which can thus be completely specified by k+2 points, say the first k+2 points. Then find the polynomial in terms of n for (each k) by polynomial curve fitting as such:

$$\sum_{i=1}^{n} i^{k}=\sum_{i=1}^{k+2}\left(\sum_{m=1}^{i} m^{k} \prod_{j=1}^{k+2} \frac{n-j}{i-j} \right)$$

where the terms in the product corresponding to j=i are omitted.

The $$\sum_{m=1}^{i} m^{k}$$ for i=1,..., k+2 terms are the $$y_{i}\mbox{'s}$$ , the "the first k+2 points" mentioned above.

I hope this was clear enough for you to follow. There's also a way using the Bernoulli numbers, I wasn't fond of it though.

-Ben

3. Nov 16, 2005

### benorin

4. Nov 16, 2005

Thank you, but isnt there some simpler way of doing this? Lagrange theorem and bernoulli numbers are not in our high school syllabus

I looked around mathworld and found that the Faulhabers formula is the correct generalization for the series?

5. Nov 16, 2005

### CarlB

Hmm. Let f(k) be the required sum. Then

$$f'(k) = kf(k-1)$$.

Now f(0) = 0 and f(1) = n. Does this help? Maybe you should write out some actual numbers and look for patterns.

Carl

6. Nov 16, 2005

### shmoe

Yes.

Given that this is a high school problem, you might consider going for a weaker conjecture than trying to guess (or look up) an explicit formula for all values of k. What can you say about the formulas you've found so far? What kind of functions are they?