A107839 a(n) = 5*a(n-1) - 2*a(n-2); a(0)=1, a(1)=5.

1, 5, 23, 105, 479, 2185, 9967, 45465, 207391, 946025, 4315343, 19684665, 89792639, 409593865, 1868384047, 8522732505, 38876894431, 177339007145, 808941246863, 3690028220025, 16832258606399, 76781236591945, 350241665746927, 1597645855550745, 7287745946259871

Offset: 0

Author

Emeric Deutsch, Jun 12 2005

Keywords

• nonn
• easy

Comments

Kekulé numbers for certain benzenoids.

This is the number of spanning, connected subgraphs of the "ladder graph" of n squares (ladder graph = the vertices and edges of the tiling of a 1 X n rectangle by unit squares). - David Pasino (davepasino(AT)yahoo.com), Sep 18 2007

a(n) equals the number of words of length n over {0,1,2,3,4} avoiding 01 and 02. - Milan Janjic, Dec 17 2015

References

• S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 78).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607. See Cor. 3.7(e).
• A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 117. Book's website
• Index entries for linear recurrences with constant coefficients, signature (5,-2).

Crossrefs

Cf. A020698, A055099 (inverse binomial transform).

Programs

Magma

I:=[1,5]; [n le 2 select I[n] else 5*Self(n-1)-2*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Dec 17 2015

Maple

a:= n-> (<<0|1>, <-2|5>>^n)[2$2]:
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 21 2020

Mathematica

a[n_] := (MatrixPower[{{1, 2}, {1, 4}}, n].{{1}, {1}})[[2, 1]]; Table[a[n], {n, 0, 40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
Table[(((5 + Sqrt[17])/2)^n - ((5 - Sqrt[17])/2)^n)/Sqrt[17], {n, 20}] // Expand (* Eric W. Weisstein, Nov 03 2024 *)
LinearRecurrence[{5, -2}, {1, 5}, 20] (* Eric W. Weisstein, Nov 03 2024 *)
CoefficientList[Series[1/(1 - 5 x + 2 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Nov 03 2024 *)

PARI

Vec(1/(1-5*x+2*x^2) + O(x^100)) \\ Altug Alkan, Dec 17 2015

Sage

[lucas_number1(n,5,2) for n in range(27)] # Zerinvary Lajos, Jun 25 2008

Formula

a(n) = A020698(n)-2*A020698(n-1) (n>=1).

a(n) = [M^(n+1)]1,2, where M is the 3 X 3 matrix defined as follows: M = [2,1,2; 1,1,1; 2,1,2]. - _Simone Severini, Jun 12 2006

a(n) = (((5 + s)/2)^(n+1) - ((5 - s)/2)^(n+1))/s with s = 17^(1/2). - David Pasino (davepasino(AT)yahoo.com), Jan 09 2009

G.f.: 1/(1 - 5*x + 2*x^2). - R. J. Mathar, Apr 07 2009

E.g.f.: exp(5*x/2)*(17*cosh(sqrt(17)*x/2) + 5*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, Jun 17 2025