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

%I #47 Sep 08 2022 08:44:40

%S 1,1,10,91,829,7552,68797,626725,5709322,52010623,473804929,

%T 4316254984,39320099785,358197153049,3263094477226,29726047448083,

%U 270797521509973,2466903741037840,22472931190850533

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

%C Generalized Fibonacci numbers.

%C 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).

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

%C 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

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

%H Vincenzo Librandi, <a href="/A015455/b015455.txt">Table of n, a(n) for n = 0..1000</a>

%H M. Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (9,1).

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

%F a(n) = Sum_{k, 0<=k<=n} 8^k*A055830(n,k). - _Philippe Deléham_, Oct 18 2006

%F 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

%F 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

%t 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 *)

%o (PARI) a(n) = polcoeff((1-(O(x^n)+8)*x)/(1-9*x-x^2),n) \\ _M. F. Hasler_, Jun 14 2008

%o (Magma) [n le 2 select 1 else 9*Self(n-1)+Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Feb 01 2015

%Y Row m=9 of A135597.

%K nonn,easy

%O 0,3

%A _Olivier Gérard_

%E Edited by _M. F. Hasler_, Jun 14 2008