A099371 Expansion of g.f.: x/(1 - 9*x - x^2).

0, 1, 9, 82, 747, 6805, 61992, 564733, 5144589, 46866034, 426938895, 3889316089, 35430783696, 322766369353, 2940328107873, 26785719340210, 244011802169763, 2222891938868077, 20250039251982456, 184473245206710181, 1680509246112374085, 15309056460218076946

Offset

0,3

Comments

For more information about this type of recurrence follow the Khovanova link and see A054413, A086902 and A178765. - Johannes W. Meijer, Jun 12 2010

For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 9's along the main diagonal and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011

For n >= 1, a(n) equals the number of words of length n-1 on alphabet {0,1,...,9} avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015

From Michael A. Allen, Mar 10 2023: (Start)

Also called the 9-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence.

a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are 9 kinds of squares available. (End)

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.

J. H. Han and M. D. Hirschhorn, Another Look at an Amazing Identity of Ramanujan, Mathematics Magazine, Vol. 79 (2006), pp. 302-304. See equation 6 on page 303.

Tanya Khovanova, Recursive Sequences

Kai Wang, On k-Fibonacci Sequences And Infinite Series List of Results and Examples, 2020.

Index entries for sequences related to Chebyshev polynomials.

Index entries for linear recurrences with constant coefficients, signature (9,1).

Formula

G.f.: x/(1 - 9*x - x^2).

a(n) = 9*a(n-1) + a(n-2), n >= 2, a(0)=0, a(1)=1.

a(n) = (-i)^(n-1)*S(n-1, 9*i) with S(n, x) Chebyshev's polynomials of the second kind (see A049310) and i^2=-1.

a(n) = (ap^n - am^p)/(ap-am) with ap:= (9+sqrt(85))/2 and am:= (9-sqrt(85))/2 = -1/ap (Binet form).

a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n-1-k, k)*9^(n-1-2*k) n >= 1.

a(n) = F(n, 9), the n-th Fibonacci polynomial evaluated at x=9. - T. D. Noe, Jan 19 2006

a(n) = ((9+sqrt(85))^n - (9-sqrt(85))^n)/(2^n*sqrt(85)). Offset 1. a(3)=82. - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009

a(p) == 85^((p-1)/2)) (mod p) for odd primes p. - Gary W. Adamson, Feb 22 2009

From Johannes W. Meijer, Jun 12 2010: (Start)

a(2n+2) = 9*A097839(n), a(2n+1) = A097841(n).

a(3n+1) = A041151(5n), a(3n+2) = A041151(5n+3), a(3n+3) = 2*A041151(5n+4).

Limit_{k -> infinity} (a(n+k)/a(k)) = (A087798(n) + A099371(n)*sqrt(85))/2.

Lim_{n->infinity} A087798(n)/A099371(n) = sqrt(85). (End)

a(n) ~ 1/sqrt(85)*((9+sqrt(85))/2)^n. - Jean-François Alcover, Dec 04 2013

a(n) = [1,0] (M^n) [0,1]^T where M is the matrix [9,1; 1,0]. - Robert Israel, Feb 01 2015

E.g.f.: 2*exp(9*x/2)*sinh(sqrt(85)*x/2)/sqrt(85). - Stefano Spezia, Apr 06 2023

Maple

F:= gfun:-rectoproc({a(n)=9*a(n-1)+a(n-2), a(0)=0, a(1)=1}, a(n), remember):
seq(F(n), n=0..30); # Robert Israel, Feb 01 2015

Mathematica

CoefficientList[Series[x/(1-9*x-x^2), {x, 0, 30}], x] (* G. C. Greubel, Apr 16 2017 *)
LinearRecurrence[{9, 1}, {0, 1}, 30] (* G. C. Greubel, Jan 24 2018 *)

Prog

(Sage)
from sage.combinat.sloane_functions import recur_gen3
it = recur_gen3(0, 1, 9, 9, 1, 0)
[next(it) for i in range(1, 22)] # Zerinvary Lajos, Jul 09 2008
(Sage) [lucas_number1(n, 9, -1) for n in range(0, 20)] # Zerinvary Lajos, Apr 26 2009
(PARI) my(x='x+O('x^30)); concat([0], Vec(1/(1-9*x-x^2)) ) \\ Charles R Greathouse IV, Feb 03 2014
(Magma) I:=[0, 1]; [n le 2 select I[n] else 9*Self(n-1) + Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 24 2018

Crossrefs

Row n=9 of A073133, A172236 and A352361.

Cf. A099372 (squares).

Cf. A041151, A054413, A086902, A087798, A099371, A097839, A178765, A243399.

Sequence in context: A033119 A033127 A361715 * A334611 A068109 A163460

Adjacent sequences: A099368 A099369 A099370 * A099372 A099373 A099374

Keyword

nonn,easy

Author

Wolfdieter Lang, Oct 18 2004

Status

approved