OFFSET
0,2
COMMENTS
a(n) is the number of words of length n over alphabet {1,2,3,4,5} such that no odd letter is followed by an odd letter.
LINKS
FORMULA
a(n) = (-(2/7)*sqrt(7)+1/2)*(1-sqrt(7))^n+((2/7)*sqrt(7)+1/2)*(1+sqrt(7))^n.
G.f.: (1+3*x)/(1-2*x-6*x^2).
EXAMPLE
For n=2 the a(2)=16 solutions are: 12, 14, 21, 22, 23, 24, 25, 32, 34, 41, 42, 43, 44, 45, 52, 54.
MAPLE
aseq:=proc(n) option remember;
if n<0 then return "seq not defined for negative indices";
elif n=0 then return 1;
elif n=1 then return 5;
else 2*aseq(n-1)+6*aseq(n-2);
end if;
end proc:
seq(aseq(n), n=0..26);
MATHEMATICA
a[0] = 1; a[1] = 5;
a[n_] := a[n] = 2*a[n - 1] + 6*a[n - 2];
Table[a[n], {n, 0, 26}]
LinearRecurrence[{2, 6}, {1, 5}, 30] (* Harvey P. Dale, Feb 20 2023 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Armend Shabani, Apr 09 2019
STATUS
approved