Finding the General Term of a Sequence

[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)

 

[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.

 

[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 (x_i,1) at that point. Then multiply the term by y_i to get the point (x_i,y_i)

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

 

[qntty]

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)

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

 

[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.

 

[qntty]

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

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.

5, 24, 63, 140, 265, 450

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

 

[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

 

[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 .

 

[mShin]

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

 

[arildno]

I am worried about the answers in this thread:

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?

 

[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.

 

[mShin]

Ok, I read up on difference calculus here:

http://www.openmathtext.org/lecture_notes/difference_calculus_generating_functions.pdf

after doing a google search for it. My next question is:

Can difference calculus be used to determine the general term for an alternating sequence? For one of the form (a^n)(n^b)?

 

[jc_cfa]

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.

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

 

[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.

 

[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