T-seqs

[Dean Hickerson]

Russell Walsmith wrote:

> Dean pointed out that the sequence S =
> 0,3,5,3,15,13,105,117,175,387,825,3397,2145,7347,7735
> is the absolute value of the sequence a(n) defined by a(1)=0, a(2)=3,
> a(3)=5, and a(n)=3a(n-1)-6a(n-2)+8a(n-3). More explicitly, a(n) = (2^(n-1) -
> ((1+sqrt(-15))/2)^n - ((1-sqrt(-15))/2)^n)/3
> 
> Way cool! I'm curious as to how that was derived, and the extent to which it
> can be extended to related sequences.

The sequence a(n) was defined in your paper as a particular entry in A^n
for a particular matrix A.  Such a sequence always satisfies a linear
recurrence of order k, if A is a k by k matrix.  In fact the coefficients
are given by the coefficients of the characteristic polynomial of A,
p(x) = det(xI-A).  This follows from the Cayley-Hamilton Theorem, which
says that A satisfies p(A)=0; multiply this equation by A^(n-k) and compare
entries on both sides.

To be honest, I didn't realize at the time that the coefficients could be
obtained that way.  I just computed enough terms of the sequence so that
I could solve the equations for the coefficients.

To get the explicit formula for a(n), I found the roots of the equation
r^3-3r^2+6r-8=0, which are r0 = 2, r1 = (1+sqrt(-15))/2, and
r2 = (1-sqrt(-15))/2, and then solved the equations
a(n) = c0 r0^n + c1 r1^n + c2 r2^n for n=0, 1, 2.

If your other sequences satisfy similar recurrences, then the same technique
will give explicit formulas for them too.

Dean Hickerson
dean at math.ucdavis.edu