A327765 a(n) is the trace of the n-th power of the 2 X 2 matrix [1 2; 3 4].

2, 5, 29, 155, 833, 4475, 24041, 129155, 693857, 3727595, 20025689, 107583635, 577969553, 3105015035, 16681014281, 89615101475, 481437535937, 2586417882635, 13894964485049, 74647658190515, 401028219922673, 2154436415994395, 11574238519817321, 62180065431075395

Offset

0,1

Comments

For n >= 1, also the number of independent vertex sets and vertex covers in the n-necklace graph. - Eric W. Weisstein, Feb 14 2026

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Eric Weisstein's World of Mathematics, Independent Vertex Set.

Eric Weisstein's World of Mathematics, Necklace Graph.

Eric Weisstein's World of Mathematics, Vertex Cover.

Index entries for linear recurrences with constant coefficients, signature (5,2).

Formula

a(n) = trace(M^n) where M is [1, 2; 3, 4].

From Colin Barker, Sep 27 2019: (Start)

G.f.: (2 - 5*x) / (1 - 5*x - 2*x^2).

a(n) = 5*a(n-1) + 2*a(n-2) for n > 1.

a(n) = ((5-sqrt(33))/2)^n + ((5+sqrt(33))/2)^n.

(End)

Maple

a:= n-> (<<0|1>, <2|5>>^n. <<2, 5>>)[1, 1]:
seq(a(n), n=0..23);  # Alois P. Heinz, Oct 07 2019

Mathematica

CoefficientList[Series[(2 - 5 x)/(1 - 5 x - 2 x^2), {x, 0, 22}], x] (* Michael De Vlieger, Sep 27 2019 *)
LinearRecurrence[{5, 2}, {2, 5}, 30] (* Harvey P. Dale, Jun 25 2020 *)
Tr /@ NestList[{{1, 2}, {3, 4}} . # &, {{1, 0}, {0, 1}}, 20] (* Eric W. Weisstein, Feb 14 2026 *)
Table[((5 - Sqrt[33])/2)^n + ((5 + Sqrt[33])/2)^n, {n, 0, 20}] // Expand (* Eric W. Weisstein, Feb 14 2026 *)

Prog

(PARI) a(n)={trace([1, 2; 3, 4]^n)} \\ Andrew Howroyd, Sep 24 2019
(PARI) Vec((2 - 5*x) / (1 - 5*x - 2*x^2) + O(x^25)) \\ Colin Barker, Sep 27 2019

Crossrefs

Cf. A100638, A124610, A233020.

Sequence in context: A073715 A104083 A257163 * A243276 A277005 A350922

Adjacent sequences: A327762 A327763 A327764 * A327766 A327767 A327768

Keyword

nonn,easy

Author

Adolf Cusmariu, Sep 24 2019

Status

approved