A104144 a(n) = Sum_{k=1..9} a(n-k); a(8) = 1, a(n) = 0 for n < 8.

0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960, 129792, 259328, 518145, 1035269, 2068498, 4132920, 8257696, 16499120, 32965728, 65866496, 131603200, 262947072, 525375999, 1049716729, 2097364960

Offset: 0

Author

Jean Lefort (jlefort.apmep(AT)wanadoo.fr), Mar 07 2005

Keywords

• nonn
• easy

Comments

Sometimes called the Fibonacci 9-step numbers.

For n >= 8, this gives the number of integers written without 0 in base ten, the sum of digits of which is equal to n-7. E.g., a(11) = 8 because we have the 8 numbers: 4, 13, 22, 31, 112, 121, 211, 1111.

The offset for this sequence is fairly arbitrary. - N. J. A. Sloane, Feb 27 2009

Links

• T. D. Noe, Table of n, a(n) for n = 0..208
• Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
• Taras Goy and Mark Shattuck, Some Toeplitz-Hessenberg Determinant Identities for the Tetranacci Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.6.8.
• Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
• Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
• Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1,1,1).

Crossrefs

Cf. A000045, A000073, A000078, A001591, A001592, A066178, A079262 (Fibonacci n-step numbers).

Cf. A255529 (Indices of primes in this sequence).

Programs

Maple

for n from 0 to 50 do k(n):=sum((-1)^i*binomial(n-8-9*i,i)*2^(n-8-10*i),i=0..floor((n-8)/10))-sum((-1)^i*binomial(n-9-9*i,i)*2^(n-9-10*i),i=0..floor((n-9)/10)):od:seq(k(n),n=0..50);a:=taylor((z^8-z^9)/(1-2*z+z^(10)),z=0,51);for p from 0 to 50 do j(p):=coeff(a,z,p):od :seq(j(p),p=0..50); # Richard Choulet, Feb 22 2010

Mathematica

a={1, 0, 0, 0, 0, 0, 0, 0, 0}; Table[s=Plus@@a; a=RotateLeft[a]; a[[ -1]]=s, {n, 50}]
LinearRecurrence[{1, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 1}, 50] (* Vladimir Joseph Stephan Orlovsky, May 25 2011 *)
With[{nn=9},LinearRecurrence[Table[1,{nn}],Join[Table[0,{nn-1}],{1}],50]] (* Harvey P. Dale, Aug 17 2013 *)

PARI

a(n)=([0,1,0,0,0,0,0,0,0; 0,0,1,0,0,0,0,0,0; 0,0,0,1,0,0,0,0,0; 0,0,0,0,1,0,0,0,0; 0,0,0,0,0,1,0,0,0; 0,0,0,0,0,0,1,0,0; 0,0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,0,1; 1,1,1,1,1,1,1,1,1]^n*[0;0;0;0;0;0;0;0;1])[1,1] \\ Charles R Greathouse IV, Jun 16 2015

PARI

A104144(n,m=9)=(matrix(m,m,i,j,j==i+1||i==m)^n)[1,m] \\ M. F. Hasler, Apr 22 2018

Formula

a(n) = Sum_{k=1..9} a(n-k) for n > 8, a(8) = 1, a(n) = 0 for n=0..7.

G.f.: x^8/(1-x-x^2-x^3-x^4-x^5-x^6-x^7-x^8-x^9). - N. J. A. Sloane, Dec 04 2011

Another form of the g.f. f: f(z) = (z^8-z^9)/(1-2*z+z^(10)), then a(n) = Sum_((-1)^i*binomial(n-8-9*i,i)*2^(n-8-10*i), i=0..floor((n-8)/10))-Sum_((-1)^i*binomial(n-9-9*i,i)*2^(n-9-10*i), i=0..floor((n-9)/10)) with Sum_(alpha(i), i=m..n)=0 for m>n. - Richard Choulet, Feb 22 2010

From N. J. A. Sloane, Dec 04 2011: (Start)

Let b be the smallest root (in magnitude) of g(x) := 1-x-x^2-x^3-x^4-x^5-x^6-x^7-x^8-x^9, b = 0.50049311828655225605926845999420216157202861343888...

Let c = -b^8/g'(b) = 0.00099310812055463178382193226558248643030626601288701...

Then a(n) is the nearest integer to c/b^n. (End)

Extensions

Edited by N. J. A. Sloane, Aug 15 2006 and Nov 11 2006

Incorrect formula deleted by N. J. A. Sloane, Dec 04 2011

Name edited by M. F. Hasler, Apr 22 2018