A015455 a(n) = 9*a(n-1) + a(n-2) for n>1; a(0) = a(1) = 1.

1, 1, 10, 91, 829, 7552, 68797, 626725, 5709322, 52010623, 473804929, 4316254984, 39320099785, 358197153049, 3263094477226, 29726047448083, 270797521509973, 2466903741037840, 22472931190850533

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

Generalized Fibonacci numbers.

As R. K. Guy suggested on the SeqFan list, the sequence could be extended "to the left side" by ..., 10, 1, 1, -8, 73, -665, 6058, -55187, 502741, -4579856, 41721445, ... by using the recurrence equation to get a(n-2) = a(n) - 9 a(n-1). The sequence 1,-8,73,... would have g.f. (1+x)/(1+9x-x^2).

For n>=1, row sums of triangle for numbers 9^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 13 2012

For n>=1, a(n) equals the numbers of words of length n-1 on alphabet {0,1,...,9} containing no subwords ii, (i=0,1,...,8). - Milan Janjic, Jan 31 2015

References

• R. K. Guy, "A further family of sequences", SeqFan mailing list (www.seqfan.eu), Jun 13 2008

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
• Tanya Khovanova, Recursive Sequences
• Index entries for linear recurrences with constant coefficients, signature (9,1).

Crossrefs

Row m=9 of A135597.

Programs

Magma

[n le 2 select 1 else 9*Self(n-1)+Self(n-2): n in [1..30]]; // Vincenzo Librandi, Feb 01 2015

Mathematica

CoefficientList[Series[(1 - 8*x)/(1 - 9*x - x^2), {x, 0, 50}], x] (* or *) LinearRecurrence[{9,1}, {1,1}, 50] (* G. C. Greubel, Dec 19 2017 *)

PARI

a(n) = polcoeff((1-(O(x^n)+8)*x)/(1-9*x-x^2),n) \\ M. F. Hasler, Jun 14 2008

Formula

G.f.: (1 - 8*x)/(1 - 9*x - x^2). - M. F. Hasler, Jun 14 2008

a(n) = Sum_{k, 0<=k<=n} 8^k*A055830(n,k). - Philippe Deléham, Oct 18 2006

a(n) = round(1/2*(9/2 - 1/2*sqrt(85))^n + 7/170*sqrt(85)*(9/2 - 1/2*sqrt(85))^n - 7/170*sqrt(85)*(9/2 + 1/2*sqrt(85))^n + 1/2*(9/2 + 1/2*sqrt(85))^n). - Alexander R. Povolotsky, Jun 13 2008

For n>=2, a(n)=F_n(9)+F_(n+1)(9), where F_n(x) is Fibonacci polynomial (cf.A049310): F_n(x) = Sum_{i=0,...,floor((n-1)/2)} C(n-i-1,i)*x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012

Extensions

Edited by M. F. Hasler, Jun 14 2008