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

1, 1, 3, 5, 23, 57, 235, 685, 2559, 8033, 28499, 92757, 320743, 1062793, 3628731, 12131069, 41160911, 138209457, 467496739, 1573172389, 5313146295, 17898525401, 60403695755, 203591898957, 686821464991, 2315556656641, 7810128376563, 26334581629685, 88815608642183

Offset: 0

Author

Paul Barry, Nov 12 2004

Keywords

• easy
• nonn

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 extremity nodes. 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 (2,7,-8).

Crossrefs

Cf. A015443, A100303, A100304.

Programs

Magma

I:=[1,1,3]; [n le 3 select I[n] else 2*Self(n-1) +7*Self(n-2) -8*Self(n-3): n in [1..31]]; // G. C. Greubel, Feb 04 2023

Mathematica

LinearRecurrence[{2,7,-8},{1,1,3},29] (* Stefano Spezia, Sep 08 2022 *)

SageMath

def A100302(n): return (3 + lucas_number1(n+1, 1, -8))/4
[A100302(n) for n in range(31)] # G. C. Greubel, Feb 04 2023

Formula

a(n) = 2*a(n-1) + 7*a(n-2) - 8*a(n-3).

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

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

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