17 June 2004

Integer Sequences

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:
  • 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.

No comments:

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.