2nd-Order Linear Recurrence Sequences
This page concerns integer sequences given by a certain type of recurrence formula, in which the next term AN is always a linear combination of the two previous terms AN-1 and AN-2. This is a subset of the type of 2nd-order recurrence formulas used by MCS.
Contents
The 1st Generalisation: Coefficient of AN-1
Divisibility of the Fibonacci Polynomials
The 2nd Generalisation: Coefficient of AN-2
Negative vs. Positive Values of a
The 3rd Generalisation: the Lucas Sequences
The 4th Generalisation: Horadam Sequences
Fibonacci Numbers
The Fibonacci numbers are the best-known example of a 2nd-order linear recurrence. The sequence is most commonly defined like this:
A0=0; A1=1; AN=AN-1+AN-2
which produces the first few terms like this:
A0=0
A1=1
A2=A1+A0 = 1+0 = 1
A3=A2+A1 = 1+1 = 2
A4=A3+A2 = 2+1 = 3
A5=A4+A3 = 3+2 = 5
A6=A5+A4 = 5+3 = 8
A7=A6+A5 = 8+5 = 13
A8=A7+A6 = 13+8 = 21
A9=A8+A7 = 21+13 = 34
A10=A9+A8 = 34+21 = 55
A11=A10+A9 = 55+34 = 89
A12=A11+A10 = 89+55 = 144
(etc.)
Divisibility Property
Some of the more interesting properties of Fibonacci numbers concern factorisation and divisibility.
To begin, it is easy to see why every 3rd Fibonacci number is even, just based on the formula AN=AN-1+AN-2. We begin with any even and odd number. The next term is even+odd, which gives odd. Then we get odd+odd which always gives even. Then we get odd+even, which is odd, followed by even+odd, which is odd, and the process repeats.
There are other similar properties: every 4th Fibonacci number is divisible by 3, and every 5th Fibonacci number is divisible by 5, and every 6th Fibonacci number is divisible by 8. These are all part of the more general property that:
For any m and n, if m is divisible by n, then Am is divisible by An.
Several examples can be seen in the terms just shown: 10 is divisible by 5, and A10=55 is divisible by A5=5. 12 is divisibe by 3, 4 and 6, and A12=144 is divisible by A3=2, A4=3 and A6=8.
The 1st Generalisation: Coefficient of AN-1
Let us now take the formula AN = AN-1 + AN-2 and add a constant k to make a new recurrence formula AN = k AN-1 + AN-2. Here is what we get for the first few terms using this new formula:
A0=0
A1=1
A2=kA1+A0 = k+0 = k
A3=kA2+A1 = k k+1 = k2+1
A4=kA3+A2 = k(k2+1)+k = k3+2k
A5=kA4+A3 = k(k3+2k)+k2+1 = k4+3k2+1
A6=kA5+A4 = k(k4+3k2+1)+k3+2k
= k5+4k3+3k
A7=kA6+A5 = k(k5+4k3+3k)+k4+3k2+1
= k6+5k4+6k2+1
A8=kA7+A6
= k(k6+5k4+6k2+1)+k5+4k3+3k
= k7+6k5+10k3+4k
(etc.)
To get the Fibonacci numbers A0045 (also MCS840) from these polynomials, let k=1. Then each polynomial gives a term of the sequence:
0 = 0
1 = 1
k = 1 = 1
k2 + 1 = 12 + 1 = 2
k3 + 2k = 13 + 2×1 = 3
k4 + 3k2 + 1 = 14 + 3×12 + 1 = 5
k5 + 4k3 + 3k = 15 + 4×13 + 3×1 = 8
(etc...)
To get A0129 (MCS1684, commonly called the Pell numberss), let k=2, and you get:
0 = 0
1 = 1
k = 2 = 2
k2 + 1 = 22 + 1 = 5
k3 + 2k = 23 + 2×2 = 12
k4 + 3k2 + 1 = 24 + 3×22 + 1 = 29
k5 + 4k3 + 3k = 25 + 4×23 + 3×2 = 70
(etc...)
To get A6190 (or MCS1692), let k=3, and you get:
0 = 0
1 = 1
k = 3 = 3
k2 + 1 = 32 + 1 = 10
k3 + 2k = 33 + 2×3 = 33
k4 + 3k2 + 1 = 34 + 3×32 + 1 = 109
k5 + 4k3 + 3k = 35 + 4×33 + 3×3 = 360
(etc...)
And to get A1076 (or MCS6748), we let k=4:
0 = 0
1 = 1
k = 4 = 4
k2 + 1 = 42 + 1 = 17
k3 + 2k = 43 + 2×4 = 72
k4 + 3k2 + 1 = 44 + 3×42 + 1 = 305
k5 + 4k3 + 3k = 45 + 4×43 + 3×4 = 1292
(etc...)
Here are the recurrence relations for these sequences:
A0045 / MCS840 : A0=0; A1=1; AN=AN-1+AN-2
A0129 / MCS1684 : A0=0; A1=1; AN=2AN-1+AN-2
A6190 / MCS1692 : A0=0; A1=1; AN=3AN-1+AN-2
A1076 / MCS6748 : A0=0; A1=1; AN=4AN-1+AN-2
(etc.)
It is easy to see that the recurrence relation for all four sequences is:
AN = k AN-1+AN-2
which of course is what we started with.
The "sequence of sequences" continues as k increases. For smaller k values most of these sequences are in Sloane's database; the first ten are: A0045, A0129, A6190, A1076, A52918, A5668, A54413, A41025, A99371, and A41041.
Fibonacci Polynomials
The polynomials in k shown above are also called the Fibonacci polynomials. It is common to arrange them in a triangle like this:
0 1 k k^2 + 1 k^3 + 2k k^4 + 3k^2 + 1 k^5 + 4k^3 + 3k k^6 + 5k^4 + 6k^2 + 1 k^7 + 6k^5 + 10k^3 + 4kIf you remove all the k's and just show the coefficients, the triangle looks like this:
0 1 1 1 1 1 2 1 3 1 1 4 3 1 5 6 1 1 6 10 4 1 7 15 10 1 1 8 21 20 5 1 9 28 35 15 1 1 10 36 56 35 6 1 11 45 84 70 21 1 .. .. .. .. .. .. ..This triangle is just a slightly rotated version of the better-known Pascal's triangle. Here are all the same numbers rotated back into the more familiar orientation:
0 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 1 8 28 56 70 1 9 36 84 1 10 45 1 11 1
Divisibility of the Fibonacci Polynomials
Now let's look at divisibility. Going back to the example sequence A0129 = (0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, ...) you can see that every other term is even, every 3rd term is divisible by 5, and every 4th term is divisible by 12.
Similarly, in A6190 = (0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, ...) every other term is divisible by 3, every 3rd term is divisible by 10, and every 4th term is divisible by 33.
Finally, in A1076 = (0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, ...) every other term is divisible by 4, every 3rd term is divisible by 17, and every 4th term is divisible by 72.
These are all examples of the more general principle stated above, which turns out to apply to all of these sequences the same way it applies to the Fobonacci numbers:
For any m and n, if m is divisible by n, then Am is divisible by An.
In fact, the Fibonacci polynomials themselves can be factored into smaller polynomials, as shown in this table:
|
(Maxima source code to generate the factored polynomials is here).
When k is Negative
So far k has been limited to positive integers. If k is zero we get a rather uninteresting sequence (0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...) (Sloane's A0035 and MCS208). How about when k is negative?
k=-1 : 0, 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, ...
The "Anti-Fibonacci numbers", -1n+1Fn (A39834 or MCS844)
k=-2 : 0, 1, -2, 5, -12, 29, -70, 169, -408, 985, -2378, ...
Anti-Pell numbers (MCS3372, not in OEIS)
k=-3 : 0, 1, -3, 10, -33, 109, -360, 1189, -3927, 12970, -42837, ...
MCS6780, not in OEIS
The pattern should be clear. These sequences all fit the polynomials and factorisations just shown, so the divisibility rule applies also. Since k is a negative number, the even-numbered Fibonacci polynomials evaluate to a positive result because those polynomials consist entirely of even powers of k. The odd-numbered Fibonacci polynomials evaluate to a negative result because those polynomials consist entirely of odd powers of k.
The 2nd Generalisation: Coefficient of AN-2
Let us now take the formula AN = k AN-1 + AN-2 and add another constant b in front of the AN-2. I will also rename k and call it a, so our constants are a and b. The recurrence formula is now AN = a AN-1 + b AN-2. For now we will keep the initial terms A0=0 and A1=1. Here is what we get for the first few terms of a sequence using this new formula:
A0=0
A1=1
A2=aA1+bA0 = a + 0 = a
A3=aA2+bA1 = a a + b = a2+b
A4=aA3+bA2 = a(a2+b) + b(a) = a3+2ab
A5=aA4+bA3 = a(a3+2ab) + b(a2+b)
= a4+3a2b+b2
A6=aA5+bA4
= a(a4+3a2b+b2) + b(a3+2ab)
= a5+4a3b+3ab2
A7=aA6+bA5
= a(a5+4a3b+3ab2) + b(a4+3a2b+b2)
= a6+5a4b+6a2b2+b3
A8=aA7+bA6
= a(a6+5a4b+6a2b2+b3)
+ b(a5+4a3b+3ab2)
= a7+6a5b+10a3b2+4a*b3
(etc.)
All of the sequences discussed in the previous sections can be generated by these polynomials, using a=k and b=1. So now let's consider what happens if we use different values for b.
When b=0 we get:
(a=1, b=0) : 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
(a=2, b=0) : 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
(a=3, b=0) : 0, 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, ...
As you can see, these sequences are basically just A0=0 followed by the powers of a starting with A1=a0=1, A2=a1=a, A3=a2, A4=a3, and so on. Since the b=0 makes the AN-2 term disappear from the recurrence formula, these sequences are really just 1st-order linear recurrences, as are all of the "powers of k" sequences for constant integer k. As you might expect, you get sequences of alternating sign when a is negative:
(a=-1, b=0) : 0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, ...
(a=-2, b=0) : 0, 1, -2, 4, -8, 16, -32, 64, -128, 256, -512, 1024, ...
(MCS421, almost identical to A122803)
When b=2 we get sequences of the form AN = a AN-1 + 2AN-2:
(a=-2, b=2) : 0, 1, -2, 6, -16, 44, -120, 328, -896, 2448, -6688, ...
(MCS13490, not in OEIS)
(a=-1, b=2) : 0, 1, -1, 3, -5, 11, -21, 43, -85, 171, -341, 683, ...
(a=0, b=2) : 0, 1, 0, 2, 0, 4, 0, 8, 0, 16, 0, 32, 0, 64, ...
(a=1, b=2) : 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, ...
The Jacobsthal numbers (A1045, MCS3362)
(a=2, b=2) : 0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, ...
(a=3, b=2) : 0, 1, 3, 11, 39, 139, 495, 1763, 6279, 22363, 79647, ...
Negative vs. Positive Values of a
These examples illustrate the general principle that if you change the sign of a, the resulting sequence is the same both with all the even-numbered terms changed in sign. The reason for this is clear from the polynomials above: for all the even-numbered terms (such as A6 = a5+4a3b+3ab2) the expression has odd powers of a in all its terms. So if you multiply a by -1 all of these terms will get multiplied by an odd power of -1, which simply makes all the terms change in sign.
For a similar reason it should be clear that whenever a is zero, all the terms of the expression for A6 are zero so A6 will be zero regardless of b. The only terms that have a nonzero value are the odd terms, which have a single part that is a power of b. So the sequences with a=0, b=k for some constant k will give us the powers of k alternating with 0's. For example (a=0, b=3) gives us (0, 1, 0, 3, 0, 9, 0, 27, 0, 81, ...) (sequence MCS835, not in OEIS)
Now that we have established these things about negative and zero a values we can proceed to look only at examples with a positive.
Here are the first few with b=3:
(a=1, b=3) : 0, 1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, ...
(a=2, b=3) : 0, 1, 2, 7, 20, 61, 182, 547, 1640, 4921, 14762, 44287, ...
(a=3, b=3) : 0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893, ...
These are fairly normal increasing sequences like what we have seen before, and similar things come from b=4 and higher positive values.
Negative b Values
When we set b=-1, we get a few surprises:
(a=1, b=-1) : 0, 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1, 1, 0, ...
This is A10892 and MCS1681). Here we have a periodic sequence that alternates between negative and positive values with a period of 6!
(a=2, b=-1) : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
The natural numbers (A1477 or MCS3369). This might come as a surprise to some readers, who are accustomed to describing this sequence by the non-recursive formula AN=N, or by AN=AN-1+1 (which is a nonlinear 1st-order recurrence).
But, it turns out, the recurrence relation AN = 2AN-1 - AN-2 amounts to the same thing, provided that you start with A0=0 and A1=1. It's pretty easy to see why, once you realise that AN-1-AN-2 is always 1, so we can replace AN = 2AN-1 - AN-2 with AN = AN-1 + (AN-1-AN-2), which is equivalent to AN = AN-1+1.
(a=3, b=-1) : 0, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, ...
This sequence gives every other Fibonacci number, that is, the even-numbered Fibonacci numbers. (It is A1906 and MCS3385). This might also be a surprise, depending on how you think the iterative calculation works ("How does it compute 8+13=21, if there is no 13 to add to the 8, and it can't do 8+8+5 because there is no 5 either?"). It is a bit of a challenge to prove the relation between this sequence and the normal Fibonacci sequence (a=b=1) using the polynomials listed above.
(a=4, b=-1) : 0, 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, ...
(a=5, b=-1) : 0, 1, 5, 24, 115, 551, 2640, 12649, 60605, 290376, ...
|
When a=0, b=1 we get (0, 1, 0, 0, 0, 0, 0, 0, 0, ...) (which is actually in the OEIS, as A63524).
The 3rd Generalisation: Lucas Sequences
So far we've been using initial values A0=0 and A1=1 and the recursive formula AN = a AN-1 + b AN-2. This class of sequences are well-known and are called Lucas sequences Un(a,-b).
There is also a second set of Lucas sequences called Vn(a,-b) with initial values A0=2 and A1=a. These use the same recursive formula AN = a AN-1 + b AN-2.
So for any particular combination of coefficients a and b, there are two Lucas sequences: One with A0=0 and A1=1, and another with A0=2 and A1=a.
They are normally parametrised with the coefficient of An-2 having the opposite sign from what we've been using so far, and the Wikipedia article Lucas sequence calls them P and Q. Using their symbols, and with the sign reversed in the An-2 coefficient, here are two examples:
U0=0; U1=1; Un = P Un-1 - Q Un-2
(e.g. the Fibonacci numbers A0045, where P=1 and Q=-1)
V0=2; V1=P; Vn = P Vn-1 - Q Vn-2
(e.g. the Lucas numbers A0032, where P=1 and Q=-1)
Both have rather important properties, by themselves and in relation to each other. As discussed above, the Un have the divisibility property; the Un and Vn together have many relationships, including:
U2n = UnVn
V2n = Vn2 - 2Qn
Un+m = (UnVm+UmVn)/2
The 2nd-order Lucas sequences include most of the more important and famous of all recurrence-generated sequences.
Lucas Sequences in the OEIS
Using the MCS sequence generator to search sequences of a limited "complexity" (measured roughly by adding the magnitudes of the initial terms and the coefficients P and Q), I made this little table of Lucas definitions that have made it into OEIS:
|
Most of these are of the U(P,Q) type, i.e. they have initial terms 0, 1. The V() sequences in the table are Vn(1,-1)=A0032, Vn(1,1)=A87204, Vn(2,1)=A7395. Vn(2,-1)=A2203. I didn't include more of the Vn type because the higher-valued initial terms add to the overall "complexity" of sequences as my MCS generator rates them. I didn't include the Q=0 row, which would contain first-order linear recurrences (the powers of P for integer P) but with an extra leading 0 or 2 term (for the Us and Vs respectively).
The 4th Generalisation: Horadam Sequences
Now we allow initial values A0 and A1 to be any two integers, while the recursive formula remains AN = a AN-1 + b AN-2.
2nd-order linear recurrence sequences have been characterised in this way as "Horadam sequences"[1]. There are four parameters, normally called p, q, r and s, but in the foregoing discussion they have been called A0, A1, b and a. The recurrence relation is:
A0=p, A1=q, AN = s AN-1+r AN-2
or equivalently:
(A0 and A1 given explicitly); AN = b AN-1+a AN-2
The Horadam sequences are characterised by a 4-element tuple (A0, A1, b, a). For example, the Lucas sequences Un(P,Q) are the Horadam sequences (0,1,-Q,P), and the Lucas Vn(P,Q) are the Horadam sequences (2,P,-Q,P).
Richard Guy's Parametrisation
On seqfan, Richard Guy wrote:
[...] You can get all second order linear recurrences (which are divisibility sequences if you take a(0)=0) by tipping up Omar Khayyam's triangle (see A11973 in OEIS):
(0) 1 1 1 1 1 2 1 3 1 1 4 3 1 5 6 1 1 6 10 4 1 7 15 10 1 1 8 21 20 5 1 9 28 35 15 1 1 10 36 56 35 6 1 11 45 84 70 21 1 .. .. .. .. .. .. ..
and then get a TWO-parameter family by multiplying the columns from right to left by a0, a1, a2, ... and the left-falling diagonals downwards by b0, b1, b2, ..., giving the sequence, which I'll call S(a,b), of polynomials
0, 1, a, a2 + b, a3 + 2a*b, a4 + 3a2 b + b2, a5 + 4a3 b + b2, a6 + 5a4 b + 6a2 b2 + b3, a7 + 6a5 b + 10a3 b2 + 4b3, ...
which factor into algebraic & primitive parts, just like Bill's. I believe that S(2x,-1) are (one sort of) Chebyshev polynomials.
The explanation is made more clear by arranging the polynomials' terms into a triangular arrangement. I fixed Guy's typos ("a5 + 4a3 b + b2" should be "a5 + 4a3 b + 3ab2" to agree with the coefficients in Omar Khayyam's triangle and to make the powers of a agree in each column):
0 1 a a^2 + b a^3 + 2ab a^4 + 3a^2b + b^2 a^5 + 4a^3b + 3ab^2 a^6 + 5a^4b + 6a^2b^2 + b^3 a^7 + 6a^5b + 10a^3b^2 + 4ab^3Guy goes on:
The lists that I gave earlier were for S(k,1) and S(k,-1). All the sequences for all a & b have almost all of the properties mentioned in my checklist, and people are beginning to add more.
which apparently refers to the following two lists he gave earlier:
For a start, compare and contrast the descriptions of A10892, A0027, A1906, A1353, A4254, A1109, A4187, A1090, A18913, A4189, A4190, A4191, A78362, A7655, A78364, A77412, A78366, A49660, A78368, A75843, A92449, A77421, A97778, A77423, A97780, A97309, A97781, A97311, A97782, A97313, and note that the varied properties that are mentioned are in fact shared by ALL of them, though rarely are more than one or two mentioned.
[...]
The companion sequence of sequences is A0045, A0129, A6190, A1076, A52918, A5668, A54413, A41025, A99371, A41041, A49666, A41061, A140455, A41085, A154597, A41113, missing, A41145, missing, A41181, missing, A41221, missing, A41265, missing, A41313, missing, A41365, A49667, A41421, missing, A41481, missing, A41545, missing, A41613, missing, A41685, missing, A41761, missing, A41841, missing, A41925, missing, A42013, missing, A42105, missing, A42201, missing, A42301, missing, A42405, missing, A42513, missing, A42625, missing, A42741,
[perhaps itself a more interesting sequence than many that are submitted?]
To give actual examples, first consider the S(k,1) sequence. This means to set a=k and b=1 in the "triangular" table of polynomials above, which gives this sequence of polynomials in k:
MAXIMA Source Code
The following is all it takes to generate and factor the Fibonacci polynomials in Maxima:
f[0]:0; f[1]:1; for i:2 thru 10 step 1 do ( f[i]: k*f[i-1] + f[i-2], print(expand(f[i]) = factor(f[i])) );The two-parameter polynomials that we get after the second generalisation can be generated just as easily:
/* Richard Guy's format of the polynomials for Horadam sequence (0,1,b,a) */ declare(a,mainvar); rg[0]:0; rg[1]:1; for i:2 thru 10 step 1 do ( rg[i]: a*rg[i-1] + b*rg[i-2], print(expand(rg[i]) = factor(rg[i])) );Many linear recurrence sequences have a generating function that is a ratio of two simple polynomials f(x) = P(x)/Q(x). The following Maxima commands demonstrate the connection between some of the simpler forms of polynomial ratios P(x)/Q(x) and the sequences generated by them:
taylor(1/(a*x^2+b*x+1), x, 0, 6); taylor(1/(a*x^3+b*x^2+c*x+1), x, 0, 6); taylor(1/((1+a*x)*(1+b*x)), x, 0, 6);Chebyshev Polynomials
The Chebyshev polynomials of the first kind can be generated by the simple linear recurrence:
T0(x) = 1
T1(x) = x
Tn+1(x) = 2xTn(x) - Tn-1(x)
The Chebyshev polynomials of the second kind use the same recurrence formula but different initial terms:
U0(x) = 1
U1(x) = 2x
Un+1(x) = 2xUn(x) - Un-1(x)
Both types of Chebyshev polynomials are an infinite series of polynomials, like the Fibonacci polynomials above. However they do not have the divisibility property; in fact, none of them is divisible by any of the others except for the trivial case of divisibility by 1. This results from the fact that they are an "orthonormal basis" for continuous differentiable functions within the interval [-1..1]: as with a Fourier series, any such function can be approximated by a linear conbination of the Chebyshev polynomials (of either kind).
Maxima can expand the Chebyshev polynomials directly from their generating functions:
(%i1) taylor((1-t*x)/(1-2*t*x+t^2),t,0,10); (%o1)/T/ 1 + x t 2 2 + (2 x - 1) t 3 3 + (4 x - 3 x) t 4 2 4 + (8 x - 8 x + 1) t 5 3 5 + (16 x - 20 x + 5 x) t 6 4 2 6 + (32 x - 48 x + 18 x - 1) t 7 5 3 7 + (64 x - 112 x + 56 x - 7 x) t 8 6 4 2 8 + (128 x - 256 x + 160 x - 32 x + 1) t 9 7 5 3 9 + (256 x - 576 x + 432 x - 120 x + 9 x) t 10 8 6 4 2 10 + (512 x - 1280 x + 1120 x - 400 x + 50 x - 1) t + . . .The polynomial in front of tn is the Tn(x), the nth Chebyshev polynomial of the first kind. Similarly, the Chebyshev polynomials of the second kind are:
(%i2) taylor(1/(1-2*t*x+t^2),t,0,10); (%o2)/T/ 1 + 2 x t 2 2 + (4 x - 1) t 3 3 + (8 x - 4 x) t 4 2 4 + (16 x - 12 x + 1) t 5 3 5 + (32 x - 32 x + 6 x) t 6 4 2 6 + (64 x - 80 x + 24 x - 1) t 7 5 3 7 + (128 x - 192 x + 80 x - 8 x) t 8 6 4 2 8 + (256 x - 448 x + 240 x - 40 x + 1) t 9 7 5 3 9 + (512 x - 1024 x + 672 x - 160 x + 10 x) t 10 8 6 4 2 10 + (1024 x - 2304 x + 1792 x - 560 x + 60 x - 1) t + . . .Somos Variant
Michael Somos, "In the Elliptic Realm", describes the even-indexed Fibonacci numbers (Sloane's A1906) thusly:
One good example of a hyperbolic sequence is the following table n : 0 1 2 3 4 5 6 7 8 9 10 ... s(n): 0 1 3 8 21 55 144 377 987 2584 6765 ... constructed starting with initial terms s(0) = 0 and s(1) = 1 . Here, each term is a constant c times the previous term minus the term before that. The recursion equation is s(n) = c*s(n-1) - s(n-2) for all n.then a little while later he describes "Chebyshev polynomials":
In other words, the following equations s(2*n+2)*s(1) = s(n+2)*s(n+1) - s(n+1)*s(n) , and s(2*n+1)*s(1) = s(n+1)*s(n+1) - s(n)*s(n) , hold for all positive n . These equations can be solved for s(n) where n is greater than 2 given any values for s(2) and s(1) but s(1) must be non-zero. When s(1) = 1 and s(2) = x , these sequences are related to Chebyshev polynomials of the second kind as follows s(n) = U(n-1, x/2).If we let s(0)=0, s(1)=1 and use the recurrence formula s(n) = cs(n-1) - s(n-2) with c=2x, then we get
s(0) = 0
s(1) = 1
s(2) = 2x
s(3) = 2x(2x) - 1 = 4x2 - 1
s(4) = 2x(4x2-1) - 2x = 8x3 - 4x
s(5) = 2x(8x3-4x) - (4x2-1)
= 16x4 - 12x2 + 1
...
which are the standard Chebyshev polynomials of the second kind. Let's look at the other definition:
s(2n+2)s(1) = s(n+2)s(n+1) - s(n+1)s(n) ,
s(2n+1)s(1) = s(n+1)s(n+1) - s(n)s(n) ,
s(1) = 1 ,
s(2) = x .
Since s(1) is 1, the definitions are equivalent to:
s(1) = 1 ,
s(2) = x ,
s(2n+1) = s(n+1)2 - s(n)2 ,
s(2n+2) = s(n+2)s(n+1) - s(n+1)s(n) .
Letting n=1, we get:
s(3) = x2-1
s(4) = s(3)x - x = x3 - 2x
Letting n=2, we get:
s(5) = s(3)2 - s(2)2 = x4-2x2+1 - x2
= x4 - 3x2 + 1
s(6) = s(4)s(3) - s(3)s(2) = (x3-2x)(x2-1) - (x2-1)x
= x5 - 4x3 + 3x
These polynomials are different, but very close: they can be converted to the standard ones by substituting "2x" everywhere we see x. For example, 3x2 becomes 3(2x)2 = 12x2.
[1] Eric W. Weisstein, "Horadam Sequence,", from MathWorld, a Wolfram Web Resource. http://mathworld.wolfram.com/HoradamSequence.html
[2] Tanya Khovanova, Recursive Sequences
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2016 Jun 12.
s.27