2ndOrder Linear Recurrence Sequences
This page concerns integer sequences given by a certain type of recurrence formula, in which the next term A_{N} is always a linear combination of the two previous terms A_{N1} and A_{N2}. This is a subset of the type of 2^{nd}order recurrence formulas used by MCS.
Contents
The 1^{st} Generalisation: Coefficient of A_{N1}
Divisibility of the Fibonacci Polynomials
The 2^{nd} Generalisation: Coefficient of A_{N2}
Negative vs. Positive Values of a
The 3^{rd} Generalisation: the Lucas Sequences
The 4^{th} Generalisation: Horadam Sequences
Fibonacci Numbers
The Fibonacci numbers are the bestknown example of a 2^{nd}order linear recurrence. The sequence is most commonly defined like this:
A_{0}=0; A_{1}=1; A_{N}=A_{N1}+A_{N2}
which produces the first few terms like this:
A_{0}=0
A_{1}=1
A_{2}=A_{1}+A_{0} = 1+0 = 1
A_{3}=A_{2}+A_{1} = 1+1 = 2
A_{4}=A_{3}+A_{2} = 2+1 = 3
A_{5}=A_{4}+A_{3} = 3+2 = 5
A_{6}=A_{5}+A_{4} = 5+3 = 8
A_{7}=A_{6}+A_{5} = 8+5 = 13
A_{8}=A_{7}+A_{6} = 13+8 = 21
A_{9}=A_{8}+A_{7} = 21+13 = 34
A_{10}=A_{9}+A_{8} = 34+21 = 55
A_{11}=A_{10}+A_{9} = 55+34 = 89
A_{12}=A_{11}+A_{10} = 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 3^{rd} Fibonacci number is even, just based on the formula A_{N}=A_{N1}+A_{N2}. 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 4^{th} Fibonacci number is divisible by 3, and every 5^{th} Fibonacci number is divisible by 5, and every 6^{th} 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 A_{m} is divisible by A_{n}.
Several examples can be seen in the terms just shown: 10 is divisible by 5, and A_{10}=55 is divisible by A_{5}=5. 12 is divisibe by 3, 4 and 6, and A_{12}=144 is divisible by A_{3}=2, A_{4}=3 and A_{6}=8.
The 1^{st} Generalisation: Coefficient of A_{N1}
Let us now take the formula A_{N} = A_{N1} + A_{N2} and add a constant k to make a new recurrence formula A_{N} = k A_{N1} + A_{N2}. Here is what we get for the first few terms using this new formula:
A_{0}=0
A_{1}=1
A_{2}=kA_{1}+A_{0} = k+0 = k
A_{3}=kA_{2}+A_{1} = k k+1 = k^{2}+1
A_{4}=kA_{3}+A_{2} = k(k^{2}+1)+k = k^{3}+2k
A_{5}=kA_{4}+A_{3} = k(k^{3}+2k)+k^{2}+1 = k^{4}+3k^{2}+1
A_{6}=kA_{5}+A_{4} = k(k^{4}+3k^{2}+1)+k^{3}+2k
= k^{5}+4k^{3}+3k
A_{7}=kA_{6}+A_{5} = k(k^{5}+4k^{3}+3k)+k^{4}+3k^{2}+1
= k^{6}+5k^{4}+6k^{2}+1
A_{8}=kA_{7}+A_{6}
= k(k^{6}+5k^{4}+6k^{2}+1)+k^{5}+4k^{3}+3k
= k^{7}+6k^{5}+10k^{3}+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
k^{2} + 1 = 1^{2} + 1 = 2
k^{3} + 2k = 1^{3} + 2×1 = 3
k^{4} + 3k^{2} + 1 = 1^{4} + 3×1^{2} + 1 = 5
k^{5} + 4k^{3} + 3k = 1^{5} + 4×1^{3} + 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
k^{2} + 1 = 2^{2} + 1 = 5
k^{3} + 2k = 2^{3} + 2×2 = 12
k^{4} + 3k^{2} + 1 = 2^{4} + 3×2^{2} + 1 = 29
k^{5} + 4k^{3} + 3k = 2^{5} + 4×2^{3} + 3×2 = 70
(etc...)
To get A6190 (or MCS1692), let k=3, and you get:
0 = 0
1 = 1
k = 3 = 3
k^{2} + 1 = 3^{2} + 1 = 10
k^{3} + 2k = 3^{3} + 2×3 = 33
k^{4} + 3k^{2} + 1 = 3^{4} + 3×3^{2} + 1 = 109
k^{5} + 4k^{3} + 3k = 3^{5} + 4×3^{3} + 3×3 = 360
(etc...)
And to get A1076 (or MCS6748), we let k=4:
0 = 0
1 = 1
k = 4 = 4
k^{2} + 1 = 4^{2} + 1 = 17
k^{3} + 2k = 4^{3} + 2×4 = 72
k^{4} + 3k^{2} + 1 = 4^{4} + 3×4^{2} + 1 = 305
k^{5} + 4k^{3} + 3k = 4^{5} + 4×4^{3} + 3×4 = 1292
(etc...)
Here are the recurrence relations for these sequences:
A0045 / MCS840 : A_{0}=0; A_{1}=1; A_{N}=A_{N1}+A_{N2}
A0129 / MCS1684 : A_{0}=0; A_{1}=1; A_{N}=2A_{N1}+A_{N2}
A6190 / MCS1692 : A_{0}=0; A_{1}=1; A_{N}=3A_{N1}+A_{N2}
A1076 / MCS6748 : A_{0}=0; A_{1}=1; A_{N}=4A_{N1}+A_{N2}
(etc.)
It is easy to see that the recurrence relation for all four sequences is:
A_{N} = k A_{N1}+A_{N2}
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 betterknown 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 3^{rd} term is divisible by 5, and every 4^{th} 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 3^{rd} term is divisible by 10, and every 4^{th} 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 3^{rd} term is divisible by 17, and every 4^{th} 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 A_{m} is divisible by A_{n}.
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 "AntiFibonacci numbers", 1^{n+1}F_{n} (A39834 or MCS844)
k=2 : 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, ...
AntiPell 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 evennumbered Fibonacci polynomials evaluate to a positive result because those polynomials consist entirely of even powers of k. The oddnumbered Fibonacci polynomials evaluate to a negative result because those polynomials consist entirely of odd powers of k.
The 2^{nd} Generalisation: Coefficient of A_{N2}
Let us now take the formula A_{N} = k A_{N1} + A_{N2} and add another constant b in front of the A_{N2}. I will also rename k and call it a, so our constants are a and b. The recurrence formula is now A_{N} = a A_{N1} + b A_{N2}. For now we will keep the initial terms A_{0}=0 and A_{1}=1. Here is what we get for the first few terms of a sequence using this new formula:
A_{0}=0
A_{1}=1
A_{2}=aA_{1}+bA_{0} = a + 0 = a
A_{3}=aA_{2}+bA_{1} = a a + b = a^{2}+b
A_{4}=aA_{3}+bA_{2} = a(a^{2}+b) + b(a) = a^{3}+2ab
A_{5}=aA_{4}+bA_{3} = a(a^{3}+2ab) + b(a^{2}+b)
= a^{4}+3a^{2}b+b^{2}
A_{6}=aA_{5}+bA_{4}
= a(a^{4}+3a^{2}b+b^{2}) + b(a^{3}+2ab)
= a^{5}+4a^{3}b+3ab^{2}
A_{7}=aA_{6}+bA_{5}
= a(a^{5}+4a^{3}b+3ab^{2}) + b(a^{4}+3a^{2}b+b^{2})
= a^{6}+5a^{4}b+6a^{2}b^{2}+b^{3}
A_{8}=aA_{7}+bA_{6}
= a(a^{6}+5a^{4}b+6a^{2}b^{2}+b^{3})
+ b(a^{5}+4a^{3}b+3ab^{2})
= a^{7}+6a^{5}b+10a^{3}b^{2}+4a*b^{3}
(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 A_{0}=0 followed by the powers of a starting with A_{1}=a^{0}=1, A_{2}=a^{1}=a, A_{3}=a^{2}, A_{4}=a^{3}, and so on. Since the b=0 makes the A_{N2} term disappear from the recurrence formula, these sequences are really just 1^{st}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 A_{N} = a A_{N1} + 2A_{N2}:
(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 evennumbered terms changed in sign. The reason for this is clear from the polynomials above: for all the evennumbered terms (such as A_{6} = a^{5}+4a^{3}b+3ab^{2}) 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 A_{6} are zero so A_{6} 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 nonrecursive formula A_{N}=N, or by A_{N}=A_{N1}+1 (which is a nonlinear 1^{st}order recurrence).
But, it turns out, the recurrence relation A_{N} = 2A_{N1}  A_{N2} amounts to the same thing, provided that you start with A_{0}=0 and A_{1}=1. It's pretty easy to see why, once you realise that A_{N1}A_{N2} is always 1, so we can replace A_{N} = 2A_{N1}  A_{N2} with A_{N} = A_{N1} + (A_{N1}A_{N2}), which is equivalent to A_{N} = A_{N1}+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 evennumbered 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 3^{rd} Generalisation: Lucas Sequences
So far we've been using initial values A_{0}=0 and A_{1}=1 and the recursive formula A_{N} = a A_{N1} + b A_{N2}. This class of sequences are wellknown and are called Lucas sequences U_{n}(a,b).
There is also a second set of Lucas sequences called V_{n}(a,b) with initial values A_{0}=2 and A_{1}=a. These use the same recursive formula A_{N} = a A_{N1} + b A_{N2}.
So for any particular combination of coefficients a and b, there are two Lucas sequences: One with A_{0}=0 and A_{1}=1, and another with A_{0}=2 and A_{1}=a.
They are normally parametrised with the coefficient of A_{n2} 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 A_{n2} coefficient, here are two examples:
U_{0}=0; U_{1}=1; U_{n} = P U_{n1}  Q U_{n2}
(e.g. the Fibonacci numbers A0045, where P=1 and Q=1)
V_{0}=2; V_{1}=P; V_{n} = P V_{n1}  Q V_{n2}
(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 U_{n} have the divisibility property; the U_{n} and V_{n} together have many relationships, including:
U_{2n} = U_{n}V_{n}
V_{2n} = V_{n}^{2}  2Q^{n}
U_{n+m} = (U_{n}V_{m}+U_{m}V_{n})/2
The 2^{nd}order Lucas sequences include most of the more important and famous of all recurrencegenerated 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 V_{n}(1,1)=A0032, V_{n}(1,1)=A87204, V_{n}(2,1)=A7395. V_{n}(2,1)=A2203. I didn't include more of the V_{n} type because the highervalued 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 firstorder 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 4^{th} Generalisation: Horadam Sequences
Now we allow initial values A_{0} and A_{1} to be any two integers, while the recursive formula remains A_{N} = a A_{N1} + b A_{N2}.
2^{nd}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 A_{0}, A_{1}, b and a. The recurrence relation is:
A_{0}=p, A_{1}=q, A_{N} = s A_{N1}+r A_{N2}
or equivalently:
(A_{0} and A_{1} given explicitly); A_{N} = b A_{N1}+a A_{N2}
The Horadam sequences are characterised by a 4element tuple (A_{0}, A_{1}, b, a). For example, the Lucas sequences U_{n}(P,Q) are the Horadam sequences (0,1,Q,P), and the Lucas V_{n}(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 TWOparameter family by multiplying the columns from right to left by a^{0}, a^{1}, a^{2}, ... and the leftfalling diagonals downwards by b^{0}, b^{1}, b^{2}, ..., giving the sequence, which I'll call S(a,b), of polynomials
0, 1, a, a^{2} + b, a^{3} + 2a*b, a^{4} + 3a^{2} b + b^{2}, a^{5} + 4a^{3} b + b^{2}, a^{6} + 5a^{4} b + 6a^{2} b^{2} + b^{3}, a^{7} + 6a^{5} b + 10a^{3} b^{2} + 4b^{3}, ...
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 ("a^{5} + 4a^{3} b + b^{2}" should be "a^{5} + 4a^{3} b + 3ab^{2}" 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[i1] + f[i2], print(expand(f[i]) = factor(f[i])) );The twoparameter 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[i1] + b*rg[i2], 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:
T_{0}(x) = 1
T_{1}(x) = x
T_{n+1}(x) = 2xT_{n}(x)  T_{n1}(x)
The Chebyshev polynomials of the second kind use the same recurrence formula but different initial terms:
U_{0}(x) = 1
U_{1}(x) = 2x
U_{n+1}(x) = 2xU_{n}(x)  U_{n1}(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((1t*x)/(12*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 t^{n} is the T_{n}(x), the n^{th} Chebyshev polynomial of the first kind. Similarly, the Chebyshev polynomials of the second kind are:
(%i2) taylor(1/(12*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 evenindexed 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(n1)  s(n2) 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 nonzero. When s(1) = 1 and s(2) = x , these sequences are related to Chebyshev polynomials of the second kind as follows s(n) = U(n1, x/2).If we let s(0)=0, s(1)=1 and use the recurrence formula s(n) = cs(n1)  s(n2) with c=2x, then we get
s(0) = 0
s(1) = 1
s(2) = 2x
s(3) = 2x(2x)  1 = 4x^{2}  1
s(4) = 2x(4x^{2}1)  2x = 8x^{3}  4x
s(5) = 2x(8x^{3}4x)  (4x^{2}1)
= 16x^{4}  12x^{2} + 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) = x^{2}1
s(4) = s(3)x  x = x^{3}  2x
Letting n=2, we get:
s(5) = s(3)^{2}  s(2)^{2} = x^{4}2x^{2}+1  x^{2}
= x^{4}  3x^{2} + 1
s(6) = s(4)s(3)  s(3)s(2) = (x^{3}2x)(x^{2}1)  (x^{2}1)x
= x^{5}  4x^{3} + 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, 3x^{2} becomes 3(2x)^{2} = 12x^{2}.
[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 2018 Aug 27. s.11