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

%I #66 Aug 31 2024 08:33:57

%S 1,1,9,17,89,225,937,2737,10233,32129,113993,371025,1282969,4251169,

%T 14514921,48524273,164643641,552837825,1869986953,6292689553,

%U 21252585177,71594101601,241614783017,814367595825,2747285859961

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

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

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

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

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

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 318

%H Milan 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 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,8)

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

%F a(n) = Sum_{k=0..n} A109466(n,k)*(-8)^(n-k). - _Philippe Deléham_, Oct 26 2008

%F G.f.: 1/(1-x-8*x^2). - _R. J. Mathar_, Apr 07 2011

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

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

%o (Sage) [lucas_number1(n,1,-8) for n in range(1, 27)] # _Zerinvary Lajos_, Apr 22 2009

%o (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

%o (PARI) Vec(1/(1-x-8*x^2)+O(x^99)) \\ _Charles R Greathouse IV_, Feb 03 2014

%Y Cf. A015442, A015441, A100302, A100303.

%K nonn,easy

%O 0,3

%A _Olivier Gérard_