Recusrive Formulae for Quadratic Functions

Idealistic

Junior Member
Joined
Sep 7, 2007
Messages
97
It's friday and I don't want to wait until monday to ask my teacher for help again. I forgot how to do it by the time i got home lol. At the moment, we are deriving explicit and recursive formulae from number sequences. I know how to derive explicit formulas from a quadratic sequence, but not a recursive formula. Here are the number sequences and their explicit formulas:

1, 4, 9 ...........................Explicit Formula is: "tn = n^2" or more familiar as (y = x^2)

2, 6, 12 .................................Explicit Formula is: "tn = n^2 + n" or more familiar as (y = x^2 + x)


Points for first sequence: (1,1), (2,4), (3,9) * Notice that the "y" values are the numbers in the first sequence.

Points for second sequence: (1,2), (2,6), (3,12) * Same principle applies as above.

*In case your wondering, I found the second common level difference (turned out to be 2) to find my "a" value (turned out to be one) via (d2 = 2a), and used three points three equations to find my "b" (turned out to be one) and "c" (turned out to be 0) values (y = ax^2 + bx + c).

Can anyone plz show me how to find the recursive formula for these number sequences? It would be much appreciated.
 
Idealistic said:
It's friday and I don't want to wait until monday to ask my teacher for help again. I forgot how to do it by the time i got home lol. At the moment, we are deriving explicit and recursive formulae from number sequences. I know how to derive explicit formulas from a quadratic sequence, but not a recursive formula. Here are the number sequences and their explicit formulas:

1, 4, 9 ...........................Explicit Formula is: "tn = n^2" or more familiar as (y = x^2)

2, 6, 12 .................................Explicit Formula is: "tn = n^2 + n" or more familiar as (y = x^2 + x)


Points for first sequence: (1,1), (2,4), (3,9) * Notice that the "y" values are the numbers in the first sequence.

Points for second sequence: (1,2), (2,6), (3,12) * Same principle applies as above.

*In case your wondering, I found the second common level difference (turned out to be 2) to find my "a" value (turned out to be one) via (d2 = 2a), and used three points three equations to find my "b" (turned out to be one) and "c" (turned out to be 0) values (y = ax^2 + bx + c).

Can anyone plz show me how to find the recursive formula for these number sequences? It would be much appreciated.

In general:

Finite Difference Series

A finite difference series is one where successive differences between the terms eventually result in a constant. For example, consider the 1 through n terms N1, N2, N3, N4,........Nn:
n...................1......2......3......4......5......6......7......8......9......10
N..................2......6.....13.....23....36....52....71....93....118....136
1st Diff..............4......7......10...13.....16....19....22....25......28
2nd Diff.................3......3......3......3......3......3......3......3

An expression can be derived enabling the definition the nth term of any finite difference series. The expression is a function of the number of successive differences required to reach the constant difference. If the first differences are constant, the expression is of the first order, i.e., N = an + b. If the second differences are constant, the expression is of the second order, i.e., N = an^2 + bn + c. Similarly, constant third differences derive from N = an^3 + bn^2 + cn + d.

Take the following example:
n.................1......2......3......4......5......6................n
N................3......9.....19.....35....59....93...............Nn
1st Diff............6.....10.....16....24....34
2nd Diff...............4.......6......8.....10
3rd Diff....................2......2......2
Using the data points (n1, N1), (n2,N2), (n3,N3), etc., we substitute them into N = an^3 + bn^2 + cn + d as follows:
(n1,N1) = (1,3) produces a(1^3) + b(1^2) + c(1) + d = 3 or a + b + c + d = 3
(n2,N2) = (2,9) produces a(2^3) + b(2^2) + c(2) + d = 9 or 8a + 4b + 2c + d = 9
(n3,N3) = (3,19) produces a(3^3) + b(3^2) + c(3) + d = 19 or 27a + 9b + 3c + d = 19
(n4,N4) = (4,35) produces a(4^3) + b(4^2) + c(4) + d = 35 or 64a + 16b + 4c + d = 35
Subtracting each successive pair yields
7a + 3b + c = 6
19a + 5b + c = 10
37a + 7b + c = 16
Again, subtracting each successive pair yields
12a + 2b = 4
18a + 2b = 6

Subtracting these yields 6a = 2 making a = 1/3, b = 0, c = 11/3, and d = -1 resulting in our final expression for the nth term of this series Nn = (n^3)/3 + (11n)/3 - 1 = (n^3 + 11n - 3)/3.
Checking it out for the 6th term we have [(6^3) + (66) - 3]/3 = [216 + 66 - 3]/3 = 279/3 = 93.


GENERAL EXPRESSIONS FOR FINITE DIFFERENCE SEQUENCES

Constant 1st differences.
n......1......2......3......4......5......6
N.....T1....T2....T3....T4....T5
Diff......d1 = d2 = .d3 = d4.

From the given data, we can write
1--a(1) + b = a + b = T1
2--a(2) + b = 2a + b = T2
3--Subtracting, a = T2 - T1
4--Substituting, T2 - T1 + b = T1 making b = 2T1 - T2

Example
n......1......2......3......4......5......6
N.....2......6.....10.....14....18....22
Diff......4......4.......4......4......4

1--a = 6 - 2 = 4
2--b = 2(2) - 6 = -2
4--Then, N = 4n - 2


Constant 2nd differences
n.....1......2.....3......4.....5.....6
N....T1...T2...T3...T4...T5...T6 where Tn stands for the nth term
Diff.....d1...d2...d3....d4...d5
Diff.........d1=d2= d3= c4 where the second dfferences are constant.

Therefore, the general expressin for the nth term is of the form N = an^2 + bn + c.
From the given data, we can write
1--a(1^2) + b(1) + c = a + b + c = T1
2--a(2^2) + b(2) + c = 4a + 2b + c = T2
3--a(3^2) + b(3) + c = 9a + 3b + c = T3
4--Subtracting (1) from (2) yields 3a + b = T2 - T1
5--Subtracting (2) from (3) yields 5a + b = T3 - T2
6--Subtracting (4) from (5) yields 2a = T3 - T2 - T2 + T1 = T1 - 2T2 + T3.
7--Therefore, a = (T1 - 2T2 + T3)/2
8--Substituting back into (4) yields (3T1 - 6T2 + 3T3)/2 + b = T2 - T1
9--Then, b = (8T2 - 5T1 - 3T3)/2
10--Substituting back into (1) yields (T1 - 2T2 + T3 + 8T2 - 5T1 - 3T3)/2 + c = T1
11--Hence, c = 3T1 - 3T2 - T3.

Example: Given the following sequence
n.....1.....2.....3.....4.....5
N....1.....5....11...19...29
Diff....4......6.....8....10
Diff........2.....2.....2.....2

Recognizing it as a finite difference sequence with 2nd differences constant at 2, the general expression for the nth term derives as follows.

From our earlier derivation
a = (1 - 2(5) + 11)/2 = 2/2 = 1
b = ((8(5) - 5(1) - 3(11))/2 = 2/2 = 1
c = 3(1) - 3(5) + 11 = -1

Therefore, N = 1(n^2) + 1(n) - 1 = n^2 + 1n - 1.



Ok i am doing finding nth terms and the chart looks like this.....
1 2 3 4 5 6 ... n
-2 0 4 10 18 27 ... ? I cant find the formula? >>

The derivation, definition, and summation of arithmetic and geometric series are well known. There is another type of series based on successive finite differences.
Assume u(n) represents a rational integral function of n terms, denoted by u1, u2, u3, u4-----u(n). From this series we can obtain another series by subtracting each term of the given series from the term following it. Lets denote this first set of differences as d1u1, d1u2, d1u3, d1u4.......etc. We can now subtract each term of the first order differences and create another series denoted by d2u1, d2u2, d2u3, d2u4.......etc. Obviously, we can continue to form further series of the 3rd, 4th, 5th,.....orders of differences. Without getting into the literal algebraic derivation, a series of this type can be defined by

u(n) = u1 + (n - 1)d1 + [(n - 1)(n - 2)d2]/1(2) + [(n - 1)(n - 2)(n - 3)d3]/1(2)3 + ......

If we denote the first term of a series of n terms as "a" with the series d1, d2, d3, ....as the first terms of the successive orders of differences, any term of the series may be derived from

a(n) = a + (n - 1)d1 + [(n - 1)(n - 2)d2]/2! + [(n - 1)(n - 2)(n - 3)d3]/3! + ..... with ! meaning factorial.

The sum of n terms of the series is given by

S(n) = na + [n(n - 1)d1]/2! + [n(n - 1)(n - 2)d2]/3! + [n(n - 1)(n - 2)(n - 3)d3]/4! + ......

This method of definition and summation will only be applicable to series where, eventually, in one of the differences series, the terms are all equal. Some examples will serve to illustrate.

Suppose you were told to erect a pyramidal pile of cannonballs with a square base that was 5 cannonballs high. You had to go get the correct amount of cannonballs from a supply house. How many would you buy?
What does a square based pyramidal ppile of cannonballs look like? One ball on top. The next layer contains 4 balls. The next 9 balls. The next 25 balls. What does this series look like?
......................1^1....2^2....3^2....4^2.....5^2....6^2
Series..............1.......4.......9......16......25.....36
1st differences......3.......5........7.......9.......11.......d1
2nd differences.........2........2........2......2..............d2 = a constant

Lets apply our two expressions to verify the 6th term and the sum of the first 6 terms.
For our series, a = 1, n = 6, d1 = 3, and d2 = 2. So, we have

a(6) = 1 + (6 - 1)3 + [(6 - 1)(6 - 2)2]/2 = 1 + 15 + 20 = 36 = 6^2.

The sum of these 6 terms ending with 36 becomes

S(6) = 6(1) + [6(6 - 1)3]/2 + [6(6 - 1)(6 - 2)2]/6 = 6 + 45 + 40 = 91.



Consider this puzzle that surfaced recently.

<< Find the number of distinct triangles in the one-hundredth (100th) shape.

/_\........./_\................../_\................../_\
.........../_\/_\............../_\/_\............../_\/_\
.............................../_\/_\/_\........../_\/_\/_\
.................................................../_\/_\/_\/_\

Following the totals of the first few will enable you to project the total in the 100th if you wish. Using our finite series relationships:

Base size.................1.....2.....3.....4.....5.....6.....7.....8.....9......10.....etc.
Triangles..................1.....5....13...26...45...71...105..148..201...265....etc.
1st difference - d1.........4....8....13....19..26....34...43....53.....64.........etc.
2nd difference - d2.3........4.....5.....6.....7.....8.....9....10....11.....12.....etc.
3rd difference - d3.........1....1.....1.....1.....1.....1.....1......1......1......1..etc.

The nth term of the series is defined by

a(n) = a + (n - 1)d1 + (n - 1)(n - 2)d2/2! + (n - 1)(n - 2)(n - 3)d3/3! + .........

where a(n) = the nth term of interest, n = the number of terms of interest, and d1, d2, d3, dn, = the first terms of the successive orders of differences until dn = a constant. Here, since you are looking for the number of triangles in the 100th figure, n = 100, a = 1, d1 = 4, d2 = 4, and d3 = 1.
Checking out the 4th figure, we get for the 4th term

a(4) = 1 + (4 - 1)4 + [(4 - 1)(4 - 2)4]/2 + [(4 - 1)(4 - 2)(4 - 3)1]/6 =
= 1 + 12 + 12 + 1 = 26.

Checking out the 5th figure, we get

a(5) = 1 + (5 - 1)4 + [(5 - 1)(5 - 2)4]/2 + [(5 - 1)(5 - 2)(5 - 3)1]/6 =
= 1 + 16 + 24 + 4 = 45.

Thus, the 100th figure will contain

a(100) = 1 + (100 - 1)4 + [(100 - 1)(100 - 2)4]/2 + [(100 - 1)(100 - 2)(100 - 3)1]/6 =
= 1 + 396 + 19,404 + 156,849 = 176,650 triangles.

The total number of triangles in all 100 figures is

S(100) = 100(1) + [100(100 - 1)4]/2 + [100(100 - 1)(100 - 2)4]/6 + [100(100 - 1)(100 - 2)(100 - 3)1]/24 =
= 100 + 19,800 + 646,800 + 3,921,225 = 4,587,925.
 
Wow. I really appreciate the help, but I just started Pre-Cal so I could only follow about 70-80% of that. You see, I know how to derive recursive formulas just not with these two sequences i listed above. BTW, the two sequences I listed are completely their own question, totally non related to each other. I'll give you an example of what I'm looking for with an easier sequence:

1, 3, 5, 7, 9 .......really basic lol.

The Explicit formula is as follows: tn = t1 + d(n - 1) * where tn = the nth term, d = the common difference, and t1 represents the first term in the sequence. Therefore, after you fil in the variables your left with: tn = (1) + (2)(n - 1) -----> tn = 2n - 1. That is the explicit formula.

The Recursive Formula on the other hand, can only be found with the term before the term you are looking for. For instants, in order to find the 5th term you need to know the fourth. The equation would look like this: tn = (tn-1) + 2. You see the difference, that way when I plug in 4 for tn, i get the third term in the sequence, 5 + 2 which is 7.

That is what I need for the quadratic sequences in my orignial post.
 
Idealistic said:
It's friday and I don't want to wait until monday to ask my teacher for help again. I forgot how to do it by the time i got home lol. At the moment, we are deriving explicit and recursive formulae from number sequences. I know how to derive explicit formulas from a quadratic sequence, but not a recursive formula. Here are the number sequences and their explicit formulas:

1, 4, 9 ...........................Explicit Formula is: "tn = n^2" or more familiar as (y = x^2)

2, 6, 12 .................................Explicit Formula is: "tn = n^2 + n" or more familiar as (y = x^2 + x)


Points for first sequence: (1,1), (2,4), (3,9) * Notice that the "y" values are the numbers in the first sequence.

Points for second sequence: (1,2), (2,6), (3,12) * Same principle applies as above.

*In case your wondering, I found the second common level difference (turned out to be 2) to find my "a" value (turned out to be one) via (d2 = 2a), and used three points three equations to find my "b" (turned out to be one) and "c" (turned out to be 0) values (y = ax^2 + bx + c).

Can anyone plz show me how to find the recursive formula for these number sequences? It would be much appreciated.

n....1....2....3....4....5
t(n).1....4....9...16...25

t(n) = [t(n-1)] + (2n - 1)


n....1....2....3....4....5
t(n).2....6...12...20...30

t(n) = [t(n-1)] + 2n
 
TchrWill said:
n....1....2....3....4....5
t(n).1....4....9...16...25

t(n) = [tn-1)] + (2n - 1)


n....1....2....3....4....5
t(n).2....6...12...20...30

t(n) = [t(n-1)] + 2n

Thanks a lot I really appreciate that. You see, my mind was so rambled over the fact that I thought that "t(n)" on the left side of the equal sign had to be the same as the "t(n)" the right side of the equation. For instants, in the second sequence, the second term is 6, so I thought that when i pluged in 6 for the t(n-1) part i would get 5; that would be incorrrect. However, now when I look at it, the t(n - 1) part is the term that came before the sixth term of the sequence which is two. I just had to think of it in trems of f(x).

Just out of curiousity, is there a method to go about doing this, or is it just looking at it and knowing?
 
Idealistic said:
TchrWill said:
n....1....2....3....4....5
t(n).1....4....9...16...25

t(n) = [tn-1)] + (2n - 1)


n....1....2....3....4....5
t(n).2....6...12...20...30

t(n) = [t(n-1)] + 2n

Thanks a lot I really appreciate that. You see, my mind was so rambled over the fact that I thought that "t(n)" on the left side of the equal sign had to be the same as the "t(n)" the right side of the equation. For instants, in the second sequence, the second term is 6, so I thought that when i pluged in 6 for the t(n-1) part i would get 5; that would be incorrrect. However, now when I look at it, the t(n - 1) part is the term that came before the sixth term of the sequence which is two. I just had to think of it in trems of f(x).

Just out of curiousity, is there a method to go about doing this, or is it just looking at it and knowing?

Do a "Google" search under Recursive Formulas.
 
For the square numbers: 1,4,9,16,25,......

youcan use \(\displaystyle \L\\(x+y)^{2}=x^{2}+xy+y^{2}\)

Let x=t and y=1:

\(\displaystyle \L\\(t+1)^{2}=t^{2}+2t+1\)

Which translates to: \(\displaystyle \L\\t_{n+1}=t_{n}+2n+1\)

The quadratic above gives you the squares.

Just a thought.

For the cubes: 1,8,27,64,125,............

\(\displaystyle \L\\(x+y)^{3}=x^{3}+3x^{2}y+3xy^{2}+y^{3}\)

Let x=t and y=1:

\(\displaystyle \L\\(t+1)^{3}=t^{3}+3t^{2}+3t+1\)

For the recurrence, you'd need \(\displaystyle a_{0}=1\) and maybe \(\displaystyle a_{1}=8\)

By the way, do you know what it is?.
 
galactus said:
For the square numbers: 1,4,9,16,25,......

youcan use \(\displaystyle \L\\(x+y)^{2}=x^{2}+xy+y^{2}\)

Let x=t and y=1:

\(\displaystyle \L\\(t+1)^{2}=t^{2}+2t+1\)

Which translates to: \(\displaystyle \L\\t_{n+1}=t_{n}+2n+1\)

The quadratic above gives you the squares.

Just a thought.

For the cubes: 1,8,27,64,125,............

\(\displaystyle \L\\(x+y)^{3}=x^{3}+3x^{2}y+3xy^{2}+y^{3}\)

Let x=t and y=1:

\(\displaystyle \L\\(t+1)^{3}=t^{3}+3t^{2}+3t+1\)

Wow. That stuff is pretty cool man, we proberly learn that stuff if the near future, thanks for giving me the heads up.
 
Top