A015443 Generalized Fibonacci numbers: a(n) = a(n-1) + 8*a(n-2).

1, 1, 9, 17, 89, 225, 937, 2737, 10233, 32129, 113993, 371025, 1282969, 4251169, 14514921, 48524273, 164643641, 552837825, 1869986953, 6292689553, 21252585177, 71594101601, 241614783017, 814367595825, 2747285859961

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

Construct a graph as follows: form the graph whose adjacency matrix is the tensor product of that of P_3 and [1,1;1,1], then add a loop at each of the extremity nodes. a(n-1) counts walks of length n between adjacent nodes. - Paul Barry, Nov 12 2004

The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 2, 9*a(n-2) equals the number of 9-colored compositions of n with all parts >= 2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011

Pisano period lengths: 1, 1, 6, 1, 24, 6, 16, 1, 6, 24, 110, 6, 56, 16, 24, 2, 16, 6, 60, 24, ... - R. J. Mathar, Aug 10 2012

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Joerg Arndt, Matters Computational (The Fxtbook), p. 318
• Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
• Index entries for linear recurrences with constant coefficients, signature (1,8)

Crossrefs

Cf. A015442, A015441, A100302, A100303.

Programs

Magma

[ n eq 1 select 1 else n eq 2 select 1 else Self(n-1)+8*Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 23 2011

Mathematica

CoefficientList[Series[1/(1-x-8*x^2), {x,0,50}], x] (* G. C. Greubel, Apr 30 2017 *)

PARI

Vec(1/(1-x-8*x^2)+O(x^99)) \\ Charles R Greathouse IV, Feb 03 2014

Sage

[lucas_number1(n,1,-8) for n in range(1, 27)] # Zerinvary Lajos, Apr 22 2009

Formula

a(n) = (((1+sqrt(33))/2)^(n+1) - ((1-sqrt(33))/2)^(n+1))/sqrt(33).

a(n) = Sum_{k=0..n} A109466(n,k)*(-8)^(n-k). - Philippe Deléham, Oct 26 2008

G.f.: 1/(1-x-8*x^2). - R. J. Mathar, Apr 07 2011

a(n) = (Sum_{1<=k<=n+1, k odd} C(n+1,k)*33^((k-1)/2))/2^n. - Vladimir Shevelev, Feb 05 2014