OFFSET
0,2
COMMENTS
The a(n) represent the number of n-move routes of a fairy chess piece starting in a given corner square (m = 1, 3, 7, 9) on a 3 X 3 chessboard. This fairy chess piece behaves like a bishop on the eight side and corner squares but on the central square the bishop turns into a raging elephant, see A175654.
LINKS
Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3, -1, -2).
FORMULA
G.f.: (1 - x + 2*x^2)/(1 - 3*x + x^2 + 2*x^3).
a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) with a(0)=1, a(1)=2 and a(2)=7.
a(n) = 2^(n+2) - 3*F(n+2) with F(n)=A000045(n).
MAPLE
nmax:=29; m:=1; A[5]:= [0, 1, 0, 1, 0, 1, 0, 1, 1]: A:=Matrix([[0, 0, 0, 0, 1, 0, 0, 0, 1], [0, 0, 0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 0, 1, 0], A[5], [0, 1, 0, 0, 0, 0, 0, 1, 0], [0, 0, 1, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 1, 0, 0, 0], [1, 0, 0, 0, 1, 0, 0, 0, 0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m, k], k=1..9): od: seq(a(n), n=0..nmax);
MATHEMATICA
Table[2^(n+2)-3Fibonacci[n+2], {n, 0, 30}] (* or *) LinearRecurrence[ {3, -1, -2}, {1, 2, 7}, 30] (* Harvey P. Dale, Dec 28 2012 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Johannes W. Meijer, Aug 06 2010, Aug 10 2010
STATUS
approved