"mixed linear recurrences"

[Brendan McKay]

* 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.