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, user91500 Feb 7 '16 at 10:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ 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. $\endgroup$ – Richard Smith Feb 7 '16 at 9:42
  • $\begingroup$ The answers of the first link give a lot of such intuitions (see the cubic pictures, for example). $\endgroup$ – Dietrich Burde Feb 7 '16 at 9:42
  • 3
    $\begingroup$ A found it: Possible dublicate of: math.stackexchange.com/questions/18983/… $\endgroup$ – 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 :)

enter image description here

  • 1
    $\begingroup$ please use Latex instead of including the picture. I know that it "takes time" but this way the answer will remain available also when the link to the image will fail. $\endgroup$ – Ant Feb 7 '16 at 10:10
  • $\begingroup$ Had access to my phone only and couldn't type on latex on this. I thought its more important to post the answer and help out someone who needs help. I would really appreciate if you didn't penalize me negatively by down rating a correct answer in the interest of people coming to the question :) $\endgroup$ – spandan madan Feb 7 '16 at 10:11
  • $\begingroup$ I will gladly upvote as soon as you type that in Latex :) My point is that stackexchange is useful because things can be found quickly and have a good formatting; it's not like this solution does not exists anywhere else on the web or can't be found using google. This place is great because you find well formatted comprehensive answer, while this is hard to look at :-) $\endgroup$ – Ant Feb 7 '16 at 10:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.