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.
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.
Comments
Post a Comment