2
$\begingroup$

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

  • 1
    possible duplicate of [why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$](http://math.stackexchange.com/questions/18983/why-is-sum-limits-k-1n-km-a-polynomial-with-degree-m1-in-n)2011-07-05
  • 0
    @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. :-)2011-07-05
  • 1
    There are multiple answers in the thread I linked. One of them talks about the [Faulhaber's formula.](http://en.wikipedia.org/wiki/Faulhaber%27s_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?2011-07-05
  • 0
    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?2011-07-05
  • 0
    @Qiaochu: I'm mostly concerned with the second. Well I've tried to follow references and at last ended up on [Umbral Calculus](http://en.wikipedia.org/wiki/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!2011-07-05
  • 0
    @Alf: yes, there are conceptual paths to writing these formulas down non-recursively but none of them are particularly easy. Of course their study is very rewarding.2011-07-05

2 Answers 2