News

Loading...

Saturday, May 24, 2008

F-sequences

F-sequences 080517 Sat - 080524 Sat

0. Introduction. F-sequences are generalizations of the Fibonacci sequence, hence the name. There are many published investigations of the Fibonacci sequence, including some wonderfully counterintuitive findings; but little has come to my attention apropos generalizations thereof. Curious. (Work on such generalizations may be out there--my research was cursory.)

Some problems look complex and difficult, but on closer analysis they break apart and are easily solved. Some problems just continue to look complex and difficult however much analysis they receive. I have not given much time to characterizing the properties of F-sequences, but so far it looks like a Type II.

1. Definitions.

1.1. Term of a Sequence. Let a be a sequence. The nth term of a is a(n). Usually, a(n) is an integer, and usually, a(0) is the first term. A sequence initially infinite before recursion will have negatively indexed terms without limit.

1.2. Fibonacci sequence has the recursion a(n+1) = a(n) + a(n-1).
(0,)1,1,2,3,5,8,13,21,34,55,...

1.3. Predecessor operators.

1.3.1. Let p(a) be an operator: p(a)a(n) = a(n-1).

1.3.2. Let q(a) be an operator: q(a)a(n) = {a(n-1) if a(n-1) exists,
0 otherwise}.

1.3.3. If a is understood from context, write {pa(n), qa(n)}.
Note that if a is not understood from context, {pa(n), qa(n)} make no more sense than {p3, q3}, since a(n) is then just a quantity.

1.4. F-sequence. Let P(x) be a polynomial in powers 0 and above of x with rational coefficients.

a is a {strict, loose} F-sequence iff a(n+1) = {P(p)a(n), P(q)a(n)} for some such P.

If a is strict, all terms specified for the initial recursion(s) must be defined initially, otherwise the sequence a is undefined; if loose, not so. If sequence a is loose and no terms are defined initially, the sequence is 0,0,0,...

E.g.: the Fibonacci sequence is an F-sequence, for which P(x) = 1+x.

2. F-sequences, cases.

2.1. P is of finite degree.
E.g.: P(x) = 1 - 2x - 5x^2 + 6x^3 = (1 - x)(1 + 2x)(1 - 3x).
a(n+1) = a(n) - 2a(n-1) - 5a(n-2) + 6a(n-3).

2.2. P is of infinite degree and a is loose.
E.g.: P(x) = 1 + x + x^2 + x^3 +..., a(0) = 1.
Sequence a is: 1,1,2,4,8,16,...

2.3. P is of infinite degree and a is strict; then (En)(Ak<=n)(a(k) must be defined initially). E.g.: P(x) = 1 + x + x^2 + x^3 +...
a(-n) = 2^(-n), n>=0. Sequence a is: ...1/8,1/4,1/2,1,1,2,4,8,16,...

3. F-sequences, properties.

3.1. WHEN does the limit of a(n+1)/a(n) exist?

3.2. When the limit of a(n+1)/a(n) exists, is it algebraic?

For case 2.1, it's trivial. For the remaining cases, I don't think that it is.

4. F-sequences, ratio of terms.

4.1. Assume that the limit of a(n+1)/a(n) exists. For simplicity, assume a is strict.
a(n+1) = P(p)a(n). Let {c(k)} be the coefficients of P.
a(n+1)/a(n) = c(0)+c(1)a(n-1)/a(n)+c(2)a(n-2)/a(n)+...
= c(0)+c(1)a(n-1)/a(n)+c(2)(a(n-2)/a(n-1))(a(n-1)/a(n))+...
Passing to the limit, r satisfies this equation: r = P(1/r).

4.2. Examples.

4.2.1. P(x) = 1 + 2x. r = 1 + 2/r. r^2 - r - 2 = 0. r = {-1,2}.
a(n+1) = a(n) + 2a(n-1).
a: 1,1,3,5,11,21,43,85,... r: 1.0,3.0,1.67,2.2,1.91,2.05,1.98,...

4.2.2. P(x) = 2 + x. r = 2 + 1/r. r^2 - 2r - 1 = 0. r = 1 ± sqrt(2).
a(n+1) = 2a(n) + a(n-1).
a: 1,2,5,12,29,70,169,408,... r: 2.0,2.5,2.4,2.417,2.414,2.4143,2.41420,... 2.4142135+.

5. F-sequences, further instructive examples.

5.1. P(x) = x + 2x^3. r = 1/r + 2/r^3. r^4 - r^2 - 2 = 0.
r = {±sqrt(-1),±sqrt(2)}. a(n+1) = a(n-1) + 2a(n-3).
a: 1,1,1,1,3,3,5,5,11,11,21,21,... r: 1.0,1.0,1.0,3.0,1.0,1.67,1.0,2.2,1.0,1.91,1.0,...

5.2. P(x) = 3(1 - x + x^2).
r = 3(1 - 1/r + 1/r^2). r^3 - 3r^2 + 3r - 3 = (r-1)^3 - 2 = 0.
r = 2^(1/3) + 1. a(n+1) = 3(a(n) - a(n-1) + a(n-2)).
a: 1,3,6,12,27,63,144,324,729,1647,...
r: 3.0,2.0,2.0,2.25,2.33,2.29,2.25,2.25,2.259,... 2.2599+.

5.3. P(x) = -3(1 + x) + x^2.
r = -3(1 + 1/r) + 1/r^2. r^3 + 3r^2 + 3r - 1 = (r+1)^3 - 2 = 0.
r = 2^(1/3) - 1. a(n+1) = -3(a(n) + a(n-1)) + a(n-2).
a: 1,-3,6,-8,3,21,-80,180,-279,217,366,-2028,5203,...
r: -3.0,-2.0,-1.33,-0.375,7.0,-3.81,-2.25,-1.55,-0.78,1.69,-5.54,-2.57,...

5.4. P(x) = 1 + x + x^2. r = 1 + 1/r + 1/r^2. r^3 - r^2 - r - 1 = 0. r = ?
a(n+1) = a(n) + a(n-1) + a(n-2).
"Cubic Fibonacci" a: 1,1,2,4,7,13,24,44,81,149,274,504,927,...
r: 1.0,2.0,2.0,1.75,1.86,1.85,1.833,1.841,1.840,1.839,1.8394,1.8393,...

5.5. P(x) = 1 - x + x^2. r = 1 - 1/r + 1/r^2. r^3 - r^2 + r - 1 = 0.
r = {1,±sqrt(-1)}. a(n+1) = a(n) - a(n-1) + a(n-2).
a: 1,2,3,2,1,2,3,2,...
Whatever initial values are chosen, sequence a is periodic with period 4.

5.6. P(x) = (1 + x)/2. r = (1 + 1/r)/2. r^2 - r/2 - 1/2 = 0. r = {-1/2,1}.
a(n+1) = (a(n) + a(n-1))/2. Write a[a(0),a(1)] to indicate initial values.
a[s+k,t+k](n) = a[s,t](n) + k. (Addition of any k simply propagates.)
So a[s,t](n) can be made to converge to any value.

5.6.1. E.g. a[0,1]: 0,1,1/2,3/4,5/8,11/16,21/32,43/64,... --> 2/3.
Proof: a[0,1](n) = b(n)/2^n. b(n) = (2^(n+1)+(-1)^n)/3.
a[0,1](n) = (2+(-1/2)^n)/3. lim a[0,1](n) = 2/3.

5.6.2. E.g. a[1,2]: 1,2,3/2,7/4,13/8,27/16,53/32,... --> 5/3.
Proof: a[1,2](n) = a[0,1](n) + 1.
lim a[1,2](n) = lim a[0,1](n) + 1 = 5/3.

5.6.3. E.g.: r[0,1] = (2/3)/(2/3) = 1. r[1,2] = (5/3)/(5/3) = 1.

1 comment:

  1. We offer WoW power leveling,World of Warcraft power leveling,Warhammer Online Power Leveling & Warhammer Power Leveling & Warhammer Online Gold,if you want buy cheap wow power leveling & honor power leveling,please come here to choose. you could find any kinds of powerleveling you want. Please remember,we are your online game helper. Please remember,we are your online game helper.please come here to choose. you could find anything you want.wow power leveling,wow power leveling,wow power leveling,wow power leveling,wow power leveling,wow powerleveling,wow powerleveling,wow powerleveling,wow powerleveling,wow powerleveling,Warhammer Online Power Leveling,war leveling,Warhammer leveling,Warhammer Power Leveling,Warhammer Online Gold,Warhammer Gold,WAR Power leveling,WAR Gold,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,wow gold,wow gold,wow gold,wow gold,wow gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,AOC Power Leveling,AGE OF CONAN Power Leveling,Warhammer Online Power Leveling,Warhammer Power Leveling,Warhammer Online Gold,Warhammer Gold,2 Moons Dil,MapleStory Mesos,Maple Story Mesos,MS Mesos,WARHAMMER ONLINE GOLD,Cheap WARHAMMER ONLINE GOLD,RuneScape Gold,RS Gold,RuneScape Money,RS Money,SilkRoad Gold,SilkRoad Online Gold,SRO Gold,EVE ISK,EVE Online ISK,Gaia Gold,2 Moons Dil,WOTLK power leveling,AOC Gold,AGE OF CONAN Gold,LOTRO Gold,Lord of the Rings Online Gold

    ReplyDelete