OFFSET
0,3
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).
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
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 *)
PROG
(PARI) a(n) = polcoeff((1-(O(x^n)+8)*x)/(1-9*x-x^2), n) \\ M. F. Hasler, Jun 14 2008
(Magma) [n le 2 select 1 else 9*Self(n-1)+Self(n-2): n in [1..30]]; // Vincenzo Librandi, Feb 01 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Edited by M. F. Hasler, Jun 14 2008
STATUS
approved