"mixed linear recurrences"

Dean Hickerson dean at math.ucdavis.edu
Wed Nov 6 08:37:22 CET 2002

Clark Kimberling asked:

> 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.
> (An example is A002531.)
> One could call A a "mixed linear recurrence".  However, this does not
> seem to a standard name. 
> The question is this:  is there a name for such sequences?  Does someone
> know a reference where such recurrences are discussed - especially for
> "order" greater than 2?

Any sequence defined by such a mix of linear recurrences (where you have
m different linear formulas depending on  n mod m) can also be defined by
a single linear recurrence.  (Offhand I don't have a proof of that, but
I'm sure it's not hard.  And that it's well-known to someone.)  For
example, your equations imply that

    a(n) = (s*u + t + v) * a(n-2) - t*v * a(n-4)

for all n.

So I don't think there's a name for such sequences, since they're a special
case of linear recurrence sequences.

Dean Hickerson
dean at math.ucdavis.edu

More information about the SeqFan mailing list