A015577 a(n+1) = 8*a(n) + 9*a(n-1), a(0) = 0, a(1) = 1.

0, 1, 8, 73, 656, 5905, 53144, 478297, 4304672, 38742049, 348678440, 3138105961, 28242953648, 254186582833, 2287679245496, 20589113209465, 185302018885184, 1667718169966657, 15009463529699912, 135085171767299209, 1215766545905692880, 10941898913151235921

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

Binomial transform is A011557, with a leading zero. - Paul Barry, Jul 09 2003

Number of walks of length n between any two distinct nodes of the complete graph K_10. Example: a(2) = 8 because the walks of length 2 between the nodes A and B of the complete graph ABCDEFGHIJ are: ACB, ADB, AEB, AFB, AGB, AHB, AIB and AJB. - Emeric Deutsch, Apr 01 2004

The ratio a(n+1)/a(n) converges to 9 as n approaches infinity. - Felix P. Muga II, Mar 09 2014

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
• Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
• Index entries for linear recurrences with constant coefficients, signature (8,9).

Crossrefs

Cf. A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499, A015531, A109500, A109501, A015552, A093134, A015565. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

Programs

Magma

[Round(9^n/10): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

Maple

seq(round(9^n/10),n=0..25); # Mircea Merca, Dec 28 2010

Mathematica

k=0;lst={k};Do[k=9^n-k;AppendTo[lst, k], {n, 0, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008 *)
Table[(9^n - (-1)^n)/10, {n,0,30}] (* or *) LinearRecurrence[{8,9}, {0,1}, 30] (* G. C. Greubel, Jan 06 2018 *)

Maxima

a[0]:0$
a[n]:=9^(n-1)-a[n-1]$
A015577(n):=a[n]$
makelist(A015577(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

PARI

A015577_vec(N=20)=Vec(O(x^N)+1/(1-8*x-9*x^2), -N-1) \\ M. F. Hasler, Jun 14 2008, edited Oct 25 2019

PARI

for(n=0,30, print1((9^n - (-1)^n)/10, ", ")) \\ G. C. Greubel, Jan 06 2018

PARI

apply( {A015577(n)=9^n\/10}, [0..25]) \\ M. F. Hasler, Oct 25 2019

Sage

[lucas_number1(n,8,-9) for n in range(0, 19)] # Zerinvary Lajos, Apr 25 2009

Formula

From Paul Barry, Jul 09 2003: (Start)

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

E.g.f. exp(4*x)*sinh(5*x)/5.

a(n) = (9^n - (-1)^n)/10. (End)

a(n) = 9^(n-1)-a(n-1). - Emeric Deutsch, Apr 01 2004

a(n) = round(9^n/10). - Mircea Merca, Dec 28 2010

Extensions

Extended by T. D. Noe, May 23 2011