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
Fibonacci Numbers
Divisibility Property
The 1st Generalization: Coefficient of AN-1
Fibonacci Polynomials
Divisibility of the Fibonacci Polynomials
When k is Negative
The 2nd Generalization: Coefficient of AN-2
The 3rd Generalization: Initial Value A1
The Horadam Sequences
MAXIMA Source Code
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 factorization 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 Generalization: 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 A000045 (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 A000129 (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 A006190 (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 A001076 (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:
A000045 / MCS840 : A0=0; A1=1; AN=AN-1+AN-2
A000129 / MCS1684 : A0=0; A1=1; AN=2AN-1+AN-2
A006190 / MCS1692 : A0=0; A1=1; AN=3AN-1+AN-2
A001076 / 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: A000045, A000129, A006190, A001076, A052918, A005668, A054413, A041025, A099371, and A041041.
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 + 4k
If 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 A000035 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 (A039834 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 factorizations 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 Generalization: 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 (A001045, 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 A010892 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 (A001477 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 realize 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 A001906 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 A063524).
The 3rd Generalization: Initial Value A1
The 4th Generalization: Horadam Sequences
2nd-order lunear recurrence sequences have been characterized 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 characterized by a 4-element tuple (A0, A1, b, a); The set of examples we juse gave are the Horadam sequences (0,1,1,k).
References
[1] Eric W. Weisstein, "Horadam Sequence,", from MathWorld, a Wolfram Web Resource. http://mathworld.wolfram.com/HoradamSequence.html
[2] Tanya Khovanova, Recursive Sequences
Richard Guy's Parametrization
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 A011973 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 the triangular arrangement (and correcting a few typos in the polynomials):
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^3
Guy 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 A010892, A000027, A001906, A001353, A004254, A001109, A004187, A001090, A018913, A004189, A004190, A004191, A078362, A007655, A078364, A077412, A078366, A049660, A078368, A075843, A092449, A077421, A097778, A077423, A097780, A097309, A097781, A097311, A097782, A097313, 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 A000045, A000129, A006190, A001076, A052918, A005668, A054413, A041025, A099371, A041041, A049666, A041061, A140455, A041085, A154597, A041113, missing, A041145, missing, A041181, missing, A041221, missing, A041265, missing, A041313, missing, A041365, A049667, A041421, missing, A041481, missing, A041545, missing, A041613, missing, A041685, missing, A041761, missing, A041841, missing, A041925, missing, A042013, missing, A042105, missing, A042201, missing, A042301, missing, A042405, missing, A042513, missing, A042625, missing, A042741,
[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 generalization 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])) );
Robert Munafo's home pages on HostMDS (c) 1996-2010 Robert P. Munafo. about contact
This work is licensed under a Creative Commons Attribution 2.5
License. Details here
s.13