# Finding the General Term of a Sequence

1. May 28, 2009

### mShin

What are some of the methods of finding the general term of a sequence of numbers? for a sequence from n = 1 to n = 6 such as:

1, 3, 6, 10, 15, 21

the general term is:

n(n+1)/2.

This is relatively easy to find using guess and check, however I was wondering if there was a general algorithm one could use to find the general term for a more complicated series such as:

3, 3, 15, 45, 99, 183.

The general term for that series is:

n^3 - 7n + 9

however I obviously reverse engineered that sequence. Finding the general term from the sequence of numbers for a complicated geometric sequence such as the one above seems daunting yet possible.

I would also like to know what branch of mathematics this question would fall under. I did a google search for series and sequences and found this forum, however not an answer to my question. Again, please discuss some of the best methods for finding the general term of a sequence or series from the numbers of the sequence. (a series is the summation of the values of a sequence)

2. May 28, 2009

### mathman

In general, you can always fit a polynomial to the given points. The degree of the polynomial will be one less than the number of points. For the examples you gave, you would get fifth degree polynomials. However, with luck, all the higher order terms would have coeficients = 0.

3. May 28, 2009

### qntty

To expand on that, the polynomial which fits it is formed as follows

Each point (say there are n+1 points) which you need to fit it to has it's own term. Each term consists of an n degree polynomial who's roots are at the x values of every point but one. Then you divide the term by the value obtained when you plug the excluded point in the n degree polynomial. This gives a value of (xi,1) at that point. Then multiply the term by yi to get the point (xi,yi)

$$P(x) = \sum_{i=0}^n y_i \prod_{j=0,j\not=i}^n \frac{x-x_j}{x_i-x_j}$$

Last edited: May 28, 2009
4. May 28, 2009

### qntty

Well it'd be [high school] algebra, although you could study polynomials in more depth in linear/modern algebra.

5. May 29, 2009

### mShin

To help me understand your solution, please show me how one would find the general term for the following sequences of numbers:

5, 24, 63, 140, 265, 450

4, -7, -26, -53, -88, -131

-1, -6, 3, 68, 255, 618

I derived these sequences from simple polynomials with positive powers and integer coefficients.

High school algebra? I didn't learn it there. I asked so that I could place the question into the correct forum category.

6. May 29, 2009

### qntty

By high school algebra I meant elementary algebra as opposed to linear. Polynomials typically aren't covered in depth that much unless it's for math team.

Well it's a tedious process for large degrees but here's one example

The points you want are (1,5), (2,24), (3,63), (4,140), (5,265), (6,450)

So you have

$$P(x)=(5)\frac{(x-2)(x-3)(x-4)(x-5)(x-6)}{(1-2)(1-3)(1-4)(1-5)(1-6)} + (24)\frac{(x-1)(x-3)(x-4)(x-5)(x-6)}{(2-1)(2-3)(2-4)(2-5)(2-6)}+(63)\frac{(x-1)(x-2)(x-4)(x-5)(x-6)}{(3-1)(3-2)(3-4)(3-5)(3-6)}$$
$$+ (140)\frac{(x-1)(x-2)(x-3)(x-5)(x-6)}{(4-1)(4-2)(4-3)(4-5)(4-6)} + (265)\frac{(x-1)(x-2)(x-3)(x-4)(x-6)}{(5-1)(5-2)(5-3)(5-4)(5-6)} +(450)\frac{(x-1)(x-2)(x-3)(x-4)(x-5)}{(6-1)(6-2)(6-3)(6-4)(6-5)}$$

Mathematica simplifies that to
$$P(x)=\frac{1}{12} \left(-360+738 x-461 x^2+161 x^3-19 x^4+x^5\right)$$
which does indeed give the right values

7. Oct 19, 2009

### jc_cfa

Could you please include the mathematica code used to insert the formula $$P(x) = \sum_{i=0}^n y_i \prod_{j=0,j\not=i}^n \frac{x-x_j}{x_i-x_j}$$
Thanks

8. Oct 19, 2009

### g_edgar

Another scheme for use by hand is to take differences. Write your sequence, then below write the differences, then the differences of that, etc. If some row is constaint, then you have your polynomial by going backward and summing...

4, -7, -26, -53, -88, -131

-11, -19, -27, -35, -43

-8, -8, -8, -8

So we get a constant in the third row. The third row is h(n) = -8, of course. The second row is then g(n)=-8n-3. And we know the formula for sum n = n(n+1)/2, so the first row is -4n(n-1)-3n+7 = -4n^2+n+7 .

9. Oct 19, 2009

### mShin

Thank you Edgar. How well known and extensive is this method? Is there anywhere I can go for additional reading materials on it?

10. Oct 19, 2009

### arildno

For an arbitrary finite sequence of numbers, there is, of course, no "right" next number.

IF we want that the explicit expression should be that polynomial of lowest degree that fits the given numbers, then of course, qntty has given the right answer.

But why is the condition that we want a polynomial expression the rigt one?

Why not a trigonometric series?

Or something entirely different?

11. Oct 19, 2009

### lurflurf

Edgar's method is very well know, what do you mean by extensive? Read about it in most any book on numerical methods, difference calculus, or interpolation. The difficulty of there kind of questions is if a particular answer is needed one must have a way (like a metric) of selecting that one asnswer from among many.

Last edited: Oct 19, 2009
12. Oct 19, 2009

### mShin

13. Oct 20, 2009

### jc_cfa

mShin, what is the true function for the first sequence {5, 24, 63, 140, 265, 450}? Thanks

14. Oct 23, 2009

### ilario980

you have got to search for "discrete calculus"

the general rule (fundamental theorem of discrete calculus) is:

if

$$g(n+1)-g(n)=f(n+1)$$

then

$$\sum^{b}_{n=a}f(n)=g(b)-g(a-1)$$

for example, the partial sums (you call it "general term") for the geometric series are:

$$f(n)=a r^{n-1}$$

$$g(n)=\frac{a r^{n}}{r-1}$$

$$\sum^{b}_{n=1}a r^{n-1}=g(b)-g(0)= \frac{a r^{b}}{r-1} - \frac{a}{r-1}$$

since

$$g(n+1)-g(n)= a r^n$$

Ilario M.

15. Oct 23, 2009

### Mensanator

You could look up Newton's Forward Difference Method (there's a clue as to how well known it is). I wrote an implementaion of it in Python. Here's the results from one of your sequences:

#
# Python
#
#
# Polynomial finder based on Newton's Forward Difference Method
#

seq = [5, 24, 63, 140, 265, 450]

$Warning: diffs array did not reach all 0's$ seq may be too small or non-polynomial
 diffs trace:
$[5, 24, 63, 140, 265, 450]$ [19, 39, 77, 125, 185]
$[20, 38, 48, 60]$ [18, 10, 12]
$[-8, 2]$ [10]
 Term0: [5, 19, 20, 18, -8, 10]
 Seq: [5, 24, 63, 140, 265, 450]
 The Polynomial:

$1$ -- * n**5
$12$
 -7
$-- * n**4$ 6

$95$ -- * n**3
$12$
 -41
$--- * n**2$ 6

$19$ -- * n**1
$1$
 5
$- * n**0$ 1

$Polynomial n Original Sequence$ ------------- --- ----------------
$5/1 0 5$ 24/1 1 24
$63/1 2 63$ 140/1 3 140
$265/1 4 265$ 450/1 5 450
## 719/1 6 None

Last edited: Oct 23, 2009