A190979 a(n) = 9*a(n-1) - 2*a(n-2), with a(0)=0, a(1)=1.

0, 1, 9, 79, 693, 6079, 53325, 467767, 4103253, 35993743, 315737181, 2769647143, 24295349925, 213118855039, 1869478995501, 16399073249431, 143852701253877, 1261876164786031, 11069180080566525, 97098868395526663, 851751455398606917, 7471565361796408927

Offset: 0

Author

Vladimir Joseph Stephan Orlovsky, May 24 2011

Keywords

• nonn
• easy

Comments

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

Links

• Colin Barker, 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).
• Index entries for linear recurrences with constant coefficients, signature (9,-2).

Crossrefs

Cf. A190958 (index to generalized Fibonacci sequences).

Programs

Magma

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

Mathematica

LinearRecurrence[{9,-2}, {0,1}, 50]

PARI

concat(0, Vec(x/(1-9*x+2*x^2) + O(x^30))) \\ Colin Barker, Feb 26 2016

SageMath

A190979 = BinaryRecurrenceSequence(9,-2,0,1)
[A190979(n) for n in (0..30)] # G. C. Greubel, Jun 17 2022

Formula

a(n) = ((9/2 + 1/2*sqrt(73))^n - (9/2 - 1/2*sqrt(73))^n)/sqrt(79). - Giorgio Balzarotti, May 27 2011

G.f.: x / (1-9*x+2*x^2). - Colin Barker, Feb 26 2016

From G. C. Greubel, Jun 17 2022: (Start)

a(n) = 2^((n-1)/2)*ChebyshevU(n-1, 9*x/(2*sqrt(2))).

E.g.f.: (2/sqrt(73))*exp(9*x/2)*sinh(sqrt(73)*x/2). (End)