12th grade stuff...

[Dreamlax]

I'm from New Zealand and not from America, so I'm not sure if I am 12th Grade (in NZ we say Year 12). But anyway, my school is rather slack, so if you think this is like 9th Grade stuff, say so.

Anyway, I am having some problems with number sequences. I can do Arithmetic and Geometric, but Recurive stuff bothers me. In case you people have different names for them, here is an example for each:

Arithmetic:
2, 4, 6, 8, 10, 12, ... nth term = 2n

Geometric:
1, 4, 9, 16, 25, ... nth term = n×n #or# (n squared)

Recursive:
1, 1, 2, 3, 5, 8, 13, ... Fibonacci.
Recursive sequences rely on the previous term (and possibly the current term) to get the next term.

I don't understand how to find the formula (so I can get the n term of the sequence) of Recursive sequences.

Cheers to anybody who can understand and/or help me.

[Guv]

I do not think there is a formula for the sum or the nth term of a Fibonacci sequence. I am sure that there are few, if any, recursive sequences for which there is a formula.

It has been a long time since I did this sort of math, so I could be wrong.

There are general formulae for the sums as well as the nth terms of arithmetic and geometric series. They will probably get to that soon in your math course.

Your example of a geometric sequence is incorrect. A geometric sequence uses a constant multiplier to get the next term. This is analogous to adding a constant value to get the next term of an arithmetic series. 3, 21, 147, 1029, 7203. . . (multiply by 7 for next term) is a geometirc series. 1, 1/2, 1/4, 1/8, 1/16. . . is another.In either geometric or arithmetic series, the first term can be almost anything.

[Sam Finch]

Guv

For the first time ever I can state categorically that you are totally and utterly wrong. There is in fact a fairly simple method of solving this type of problem for all sequences like this.

A recursive sequence can be defined as folows

T(n+p) = a*T(n+(p-1)) + b*T(n+(P-2)) + c*T(n+(p-3)) + ... + d*T(n)

where T(n) = the nth term of the sequence.

we also need to define the first p terms.

we can rearange the definition into this form


T(n+p) - a*T(n+(p-1)) - b*T(n+(P-2)) - c*T(n+(p-3)) - ... - d*T(n) = 0

It can be shown (with some difficulty) that if we convert this into a polynomial equation.

x^p - a*(x^(p-1)) - b*(x^(P-2)) - c*(x^(p-3)) - ... - d = 0

and solve it to get solutions s(1), s(2), s(3), ---, s(p) then

T(n) = A*(s(1)^n) + B*(s(2)^n) + C*(s(3)^n) + ..... + D*(s(p)^n)

as we know the first p terms, by equating them with this formula for the first p values of n we get a set of p simultanious equations to work out the values of the constants.

The fibbionacci sequence involves complex numbers (it's polynomial has complex solutions), so I'll give you a different one as an example.


The first 2 Terms are 0and 1, Get the next term by multiplying the previous term by 5 and then subtracting 6 times the term before that ( 5*1 - 0 = 5) (5*5 - 6 = 19)(5*19 - 6*5 = 65)

0,1,5,19,65,....

ie T(n+2) = 5*T(n+1) - 6*T(n)


T(n+2) - 5*T(n+1) + 6*T(n) = 0


gives us the equation

x^2 - 5x + 6 = 0

which has solutions 2 and 3.

so T(n) = a*(2^n) + b*(3^n)
to find a and b we have the pair of simultainious equations

T(1) = a*(2^1) + b*(3^1) = 0
T(2) = a*(2^2) + b*(3^2) = 1

or

2a + 3b = 0
4a + 9b = 1

a = - 1/2
b = 1/3

so T(n) = (1/3)*(3^n) - (1/2)*(2^n)

or more simply T(n) = (3^(n-1)) - (2^(n-1))

and so for the 5th term (65) we get 3^4 - 2^4 = 81 - 16 = 65.

Ta Daa.

[Guv]

Sam: Looks like you got me. I really did not think there was a way to cope with such series. I will not try to weasel out by claiming that I hedged a bit.

I wish I could claim that this is the first time in my life that I have ever been wrong. Actually, I could make the claim: It just would not be true.

I am amused by the reference to your method as simple.

I checked your formula for quite a few terms of the simple sequence you used as an example. It worked for the first 10, which makes me believe it would work for all.

I fought through the mess you suggested to come up with an equation for the Fibonacci sequence. The equation I got worked for 0, 1, 1 but failed from there on out. I probably made some mistake. The algebra was messy.

An Internet search led me to many sites, one of which had a somewhat messy formula for the nth term of the Fibonacci sequence. The derivation at that site seemed more complicated than what you described, but did not involve complex numbers anywhere.

I did not find any formula for the sum of a Fibonacci series, so perhaps I can claim to be half right, or maybe just half-a**ed/half-witted.

I have attached a zipped Rich Text Format File (Fibonacci.rtf) with the formula I discovered. .rtf files can be opened with several Word Processors: Wordpad, MS Word, & Corel WordPerfect.

Not sure my version of ZIP is compatible with others. Good luck if you try to download it.

[HarryW]

All zip programs work with the same algorithm (i'm fairly sure that's true anyway), so there's no need to worry.

I use the old DOS version of PKZip/Unzip quite a lot, since that's what I'm used to using. It's only a hundred and something k in size, doesn't need any fancy Windows installation, and can deal with long file names if it's in a Win32 environment. It comes in very handy when you only have access to a floppy disk drive to get files from one computer to another, since it fits on one disk. Gosh, I'm a veritable walking advert :) (you can get it from www.pkunzip.com if you're interested)

Sam - haven't seen you around here in ages.

Remember I am only 12th grade (at a school which claims it is smokefree, but lets people off for smoking) and we haven't even studied anything about polynomials. Mind you, some guy in the same level as me (he goes to my school) last year got about 98% or somthing above 90 in Grade 13 Maths and he is heading over to Washington for some competition.

Anyway I realise I got my definition of a geometric sequence wrong. My teacher said it is multiplied by a constant number, and that includes the term number. Then someone told him he was wrong because the term number isn't constant. I just forgot about thay guy saying that.