Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Most programmers (including me) are painfully aware of quadratic behavior resulting from a loop that internally performs 1, 2, 3, 4, 5 and so on operations per iteration,

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

It’s very easy to derive, e.g. considering the double of the sum like $(1+2+3) + (3+2+1) = 3\times4$ .

For the sum of squares there is a very similar formula,

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

But the only way I found to derive that was to assume it would sum to a cubic polynomial $f(x)=Ax^3+Bx^2+Cx+D$, and solve for $f(n)-f(n-1)=n^2$.

I’m guessing that there is a much simpler system and concept here, generalizing to $\sum_{i=1}^n i^k$?

share|improve this question
1  
    
@Aryabhata: thanks, but I'm more like fishing for general formula and underlying easy way to understand it (how it occurs). I'm not a matehmatician. :-) –  Alf P. Steinbach Jul 5 '11 at 15:38
1  
There are multiple answers in the thread I linked. One of them talks about the Faulhaber's formula.. If you understand a bit of integral calculus, Euler Summation gives you an easy way to see the formula, and a more elementary answer is given by Derek Jennings. Perhaps you would like to edit the question to ask for clarification of one of those answers there? –  Aryabhata Jul 5 '11 at 15:52
    
There seem to be two questions here: 1) why is the sum a polynomial? 2) given that it is a polynomial, what's a conceptual way to find its coefficients? The linked question primarily addresses the first question but also addresses the second; are you more concerned about the second? –  Qiaochu Yuan Jul 5 '11 at 19:35
    
@Qiaochu: I'm mostly concerned with the second. Well I've tried to follow references and at last ended up on Umbral Calculus in Wikipedia, like, the Dark Side of math, and my head is spinning. I head some idea that there would be some pretty simple system, but alas, it doesn't seem to... Anyway, thanks to all here! –  Alf P. Steinbach Jul 5 '11 at 20:38

2 Answers 2

These "power sum" polynomials are known as Bernoulli polynomials, and have been studied for centuries, and there is a vast literature about them. There are many inductive formulae relating them. As you observed, the right thing to do is to consider a polynomial $f_{k}(x)$ with $f_{k}(0) = 0$ and $f_{k}(x+1) - f_{k}(x) = (x+1)^{k}$, where $k$ is a chosen positive integer. Notice that is a polnomial of finite degree satisfies this equation for all positive integers, then it must satisfy it for all real $x$, and furthermore, it is unique. Notice also that, given such a polynomial exists, we must have $f(-1) =0$, so that both $x$ and $x+1$ must be factors for $f_{k}(x)$ for every $k$, given that $f_{k}$ exists. How do we know that the polynomial $f_{k}(x)$ always exists? There are many ways to see this. I like an inductive approach. The polynomial $f_{1}(x) = \frac{x(x+1)}{2}$ gets us started. How can we find $f_{k+1},$ given $f_{k}$? Well, one way to do it is to notice that if we had $f_{k+1}$ and differentiated its defining equation, we would obtain $f_{k+1}^{'}(x+1) - f_{k+1}^{'}(x) = (k+1)(x+1)^{k}$, which is nearly the defining equation for $f_{k}$, apart from a factor $k+1$ and the possible addition of a constant. Hence, if it is to exist, we should have $f_{k+1}(x) = c(k+1)x + d(k+1) + (k+1)\int_{-1}^{x} f_{k}(t) dt$ for certain constants $c(k+1)$ and $d(k+1)$. We can determine the constants $c(k+1)$ and $d(k+1)$. Since we need $f_{k+1}(0) = 0$, we must have $d(k+1) = -(k+1)\int_{-1}^{0} f_{k}(t)dt$. Since we need $f_{k+1}(-1) = 0$, we need $c(k+1) = d(k+1)$. Hence we have uniquely specified a polynomial $f_{k+1}$ (of degree $k+2$) with the right properties. It is $f_{k+1}(x) = -(x+1)(k+1)\int_{-1}^{0}f_{k}(t)dt + (k+1) \int_{-1}^{x} f_{k}(t)dt$.

This can be rewritten as $$ \frac{f_{k+1}(x)}{k+1} = x \int_{0}^{-1}f_{k}(t)dt + \int_{0}^{x} f_{k}(t)dt$$ if preferred.

share|improve this answer

Your derivation is actually quite nice. I doubt you'll find some very conceptually simple way of computing the general formula (so that you could look at it and say: aha! that was why...!). There are some "visual proofs" for power one and two but I don't think they can be generalized. Mathematically, for can look here and here. But this, I guess, is not what you're looking for.

share|improve this answer
    
I really liked your answer over at the second "here". Because it was in a sense very clean and very surprising. But you're right, I was looking for something more geometrical are numberish. :-) –  Alf P. Steinbach Jul 5 '11 at 16:32

Your Answer

 
discard

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.