- Use various sum manipulation rules and (maybe) some sums whose closed-form you already know to find the answer by "construction".
- Compute the first few numbers of the sequence, guess the answer by using various heuristics and prove by induction. An example "heuristic" is transforming the sum into an integral, computing the integral and then search for answers with a similar form. Eg. by knowing that integ(x^n) is proportional to x^(n+1) you can guess that 1+4+9+...+N^2 has the form a+bN+cN^2+dN^2.
- Or, if you are in a hurry, use the On-line Encyclopedia of Integer Sequences to find the formula from the first few terms :). As a bonus you will also get references to articles and/or web sites that give more details.
17 June 2004
Remember high school days with all kinds of integer sequences? Do you remember a closed form formula for the sum of the first N integer numbers: 1+2+...+N? Do you remember the sum of the first N squares: 1+4+9+...+N^2? If you ever need to answer such questions some possible approaches are: