"mixed linear recurrences"
Brendan McKay
bdm at cs.anu.edu.au
Mon Nov 4 23:55:22 CET 2002
* Kimberling, Clark <ck6 at evansville.edu> [021105 05:41]:
> Let A be a sequence given by initial values a(0) and a(1), and for n>1,
> let
>
> a(n) = s*a(n-1) + t*a(n-2) if n is even,
> a(n) = u*a(n-1) + v*a(n-2) if n is odd.
The canonical approach is to treat it as a two-variable linear
recurrence. If b(n) = a(2*n) and c(n) = a(2*n+1) then
b(n) = s*c(n-1) + t*b(n-1)
c(n) = u*b(n) + v*c(n-1) = (u*s+v)*c(n-1) + u*t*b(n-1)
(Assuming I made no mistake; anyway, something like that.)
Now write A(n) to be the column vector [b(n) c(n)] and you
have that A(n) = M * A(n-1) where M is the matrix
[t s]
[u*t u*s+v]
so the solution is A(n) = M^n A(0).
An explicit expression for M^n can be found using the
eigenvalues and eigenvectors of M.
Brendan.
More information about the SeqFan
mailing list