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

1, 8, 71, 631, 5608, 49841, 442961, 3936808, 34988311, 310957991, 2763633608, 24561744481, 218292066721, 1940066856008, 17242309637351, 153240719880151, 1361924169284008, 12104076803675921, 107574767063799281, 956068826770517608

Offset: 0

Author

Joe Keane (jgk(AT)jgk.org), May 18 2002

Keywords

• nonn
• easy

Comments

A Pellian sequence.

In general, Sum_{k=0..n} binomial(2n-k,k)j^(n-k) = (-1)^n*U(2n, i*sqrt(j)/2), i=sqrt(-1). - Paul Barry, Mar 13 2005

a(n) = L(n,9), where L is defined as in A108299; see also A057081 for L(n,-9). - Reinhard Zumkeller, Jun 01 2005

Number of 01-avoiding words of length n on alphabet {0,1,2,3,4,5,6,7,8} which do not end in 0. - Tanya Khovanova, Jan 10 2007

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

Positive values of x (or y) satisfying x^2 - 9xy + y^2 + 7 = 0. - Colin Barker, Feb 09 2014

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Alex Fink, Richard K. Guy, and Mark Krusemeyer, Partitions with parts occurring at most thrice, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114. See Section 13.
• Tanya Khovanova, Recursive Sequences
• J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
• Index entries for linear recurrences with constant coefficients, signature (9,-1).

Crossrefs

Cf. A057081, A056918.

Row 9 of array A094954.

Cf. similar sequences listed in A238379.

Programs

Magma

I:=[1,8]; [n le 2 select I[n] else 9*Self(n-1)-Self(n-2): n in [1..30]]; // Vincenzo Librandi, Feb 10 2014

Mathematica

CoefficientList[Series[(1 - x)/(1 - 9 x + x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Feb 10 2014 *)
LinearRecurrence[{9,-1},{1,8},30] (* Harvey P. Dale, Sep 24 2015 *)

Sage

[lucas_number1(n, 9, 1) - lucas_number1(n-1, 9, 1) for n in range(1, 19)]  # Zerinvary Lajos, Nov 10 2009

Formula

a(n) ~ (1/11)*sqrt(11)*((1/2)*(sqrt(11) + sqrt(7)))^(2*n+1).

Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i); then q(n, 7) = a(n). - Benoit Cloitre, Nov 10 2002

a(n)*a(n+3) = 63 + a(n+1)*a(n+2). - Ralf Stephan, May 29 2004

a(n) = (-1)^n*U(2n, i*sqrt(7)/2), U(n, x) Chebyshev polynomial of second kind, i=sqrt(-1). - Paul Barry, Mar 13 2005

G.f.: (1-x)/(1-9*x+x^2). - Philippe Deléham, Nov 03 2008

a(n) = A018913(n+1) - A018913(n). - R. J. Mathar, Jun 07 2013

Extensions

More terms from Vincenzo Librandi, Feb 10 2014