Finding an expression for the sum of n tems of the series $1^2 + 2^2 + 3^2 + … + n^2$ [duplicate]

Possible Duplicate:
why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

I know that if you have a non-arithmetic or geometric progression, you can find a sum $S$ of a series with the formula $S=f(n+1)-f(1)$ where the term $u_n$ is $u_n=f(n+1)-f(n)$. Then you can prove that with induction.

What I don't understand is how I should go about finding the function $f(n)$. For example if I want to calculate the sum to $n$ terms of the series $1^2 + 2^2 + 3^2 + ... + n^2$ then, according to my textbook, my $f(n)$ function should be a polynomial with degree one more than the degree of a term in my sequence - so because the $n$th term in the sequence is $P(n)=n^2$ then the function $f(n)$ should be $f(n)=an^3+bn^2+cn+d$. But how did they know that it should look like that and how do I gain some intuition into finding that function to help me solve similar problems in the future?

marked as duplicate by Dietrich Burde, user228113, Claude Leibovici, J.-E. Pin, user91500Feb 7 '16 at 10:36

• I don't think it should be considered a duplicate because it's not the proof that I need help with but rather gaining some intuition with finding the function $f(n)$ in these types of problems. – Richard Smith Feb 7 '16 at 9:42
• The answers of the first link give a lot of such intuitions (see the cubic pictures, for example). – Dietrich Burde Feb 7 '16 at 9:42
• A found it: Possible dublicate of: math.stackexchange.com/questions/18983/… – Imago Feb 7 '16 at 9:53

This works for sums of $p$th powers of $k$ because of the fact that $(n+1)^{p+1}-n^{p+1},$ when expanded by the binomial theorem, will have no $n^{p+1}$ term, and so when summed only uses powers up to the $p$th power. Also before expanding it, its sum "telescopes" (all terms cancel but two, or all but one if you sum starting at $0.$). Also once you accept the fact you can use the first few values of the sum to determine the constants in front of the powers, as in the $a,b,c,d$ of your example, by solving a linear system.
Here's how you do it! I've attached a picture I found on the internet since typing it takes time. This is a general approach that works for the sum of the $k^{th}$ power of n consecutive integers for all possible values of n. Hope it helps :) 