A100304 Expansion of (1 - x - 6*x^2)/(1 - x - 8*x^2).

1, 0, 2, 2, 18, 34, 178, 450, 1874, 5474, 20466, 64258, 227986, 742050, 2565938, 8502338, 29029842, 97048546, 329287282, 1105675650, 3739973906, 12585379106, 42505170354, 143188203202, 483229566034, 1628735191650, 5494571719922, 18524453253122, 62481027012498

Offset

0,3

Comments

Construct a graph as follows: form the graph whose adjacency matrix is the tensor product of that of P_3 and [1,1;1,1], then add a loop at each of the 'internal' nodes. (Spectrum : [0^3; 1; (1-sqrt(33))/2;(1+sqrt(33))/2]). a(n) counts closed walks of length n at each of the extremity nodes.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (1,8).

Formula

a(n) = 3*0^n/4 + (2/sqrt(33))*( ((1 + sqrt(33))/2)^(n-1) - ((1 - sqrt(33))/2)^(n-1) ).

E.g.f.: (99 + exp(x/2)*(33*cosh(sqrt(33)*x/2) - sqrt(33)*sinh(sqrt(33)*x/2)))/132. - Stefano Spezia, Sep 08 2022

a(n) = (3/4)*[n=0] + 2*A015443(n-2). - G. C. Greubel, Feb 04 2023

Mathematica

LinearRecurrence[{1, 8}, {1, 0, 2}, 27] (* Stefano Spezia, Sep 08 2022 *)

Prog

(Magma) [1] cat [n le 2 select 2*(n-1) else Self(n-1) +8*Self(n-2): n in [1..30]]; // G. C. Greubel, Feb 04 2023
(SageMath)
def A100304(n): return (3/4)*int(n==0) + 2*lucas_number1(n-1, 1, -8)
[A100304(n) for n in range(31)] # G. C. Greubel, Feb 04 2023

Crossrefs

Essentially half A100303.

Cf. A015443, A100302 (partial sums), A100305.

Sequence in context: A055735 A168296 A205454 * A213271 A096190 A136434

Adjacent sequences: A100301 A100302 A100303 * A100305 A100306 A100307

Keyword

easy,nonn

Author

Paul Barry, Nov 12 2004

Status

approved