Register to reply

Finding the General Term of a Sequence

Share this thread:
mShin
#1
May28-09, 07:04 PM
P: 4
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)
Phys.Org News Partner Mathematics news on Phys.org
Mathematicians analyse new 'racetrack memory' computer device
Children's book explores Really Big Numbers
'Moral victories' might spare you from losing again
mathman
#2
May28-09, 07:33 PM
Sci Advisor
P: 6,040
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
#3
May28-09, 10:26 PM
qntty's Avatar
P: 290
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)

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

qntty
#4
May28-09, 10:38 PM
qntty's Avatar
P: 290
Finding the General Term of a Sequence

Quote Quote by mShin View Post
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
#5
May29-09, 12:18 PM
P: 4
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
#6
May29-09, 04:24 PM
qntty's Avatar
P: 290
Quote Quote by mShin View Post
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

[tex] 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)} [/tex]
[tex]+ (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)} [/tex]

Mathematica simplifies that to
[tex]P(x)=\frac{1}{12} \left(-360+738 x-461 x^2+161 x^3-19 x^4+x^5\right)[/tex]
which does indeed give the right values
jc_cfa
#7
Oct19-09, 01:11 AM
P: 2
Could you please include the mathematica code used to insert the formula [tex]
P(x) = \sum_{i=0}^n y_i \prod_{j=0,j\not=i}^n \frac{x-x_j}{x_i-x_j}
[/tex]
Thanks
g_edgar
#8
Oct19-09, 09:02 AM
P: 607
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
#9
Oct19-09, 11:55 AM
P: 4
Thank you Edgar. How well known and extensive is this method? Is there anywhere I can go for additional reading materials on it?
arildno
#10
Oct19-09, 12:03 PM
Sci Advisor
HW Helper
PF Gold
P: 12,016
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
#11
Oct19-09, 01:53 PM
HW Helper
P: 2,263
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
#12
Oct19-09, 03:17 PM
P: 4
Ok, I read up on difference calculus here:

http://www.openmathtext.org/lecture_..._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
#13
Oct20-09, 02:34 AM
P: 2
Quote Quote by mShin View Post
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
#14
Oct23-09, 11:04 AM
P: 24
you have got to search for "discrete calculus"

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

if

[tex]g(n+1)-g(n)=f(n+1)[/tex]

then

[tex]\sum^{b}_{n=a}f(n)=g(b)-g(a-1)[/tex]


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

[tex]f(n)=a r^{n-1}[/tex]

[tex]g(n)=\frac{a r^{n}}{r-1}[/tex]


[tex]\sum^{b}_{n=1}a r^{n-1}=g(b)-g(0)= \frac{a r^{b}}{r-1} - \frac{a}{r-1}[/tex]

since

[tex]g(n+1)-g(n)= a r^n[/tex]


Ilario M.
Mensanator
#15
Oct23-09, 07:14 PM
P: 105
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


Register to reply

Related Discussions
A sequence can be start by the a2 . term? Set Theory, Logic, Probability, Statistics 6
Finding nth term of a sequence (explicit formula) Precalculus Mathematics Homework 3
Finding kth term of a sequence Calculus & Beyond Homework 2
Geometric sequence, determining the value of the first term General Math 8
General term of the sequence, if it exists General Math 9