A015565 a(n) = 7*a(n-1) + 8*a(n-2), a(0) = 0, a(1) = 1.

0, 1, 7, 57, 455, 3641, 29127, 233017, 1864135, 14913081, 119304647, 954437177, 7635497415, 61083979321, 488671834567, 3909374676537, 31274997412295, 250199979298361, 2001599834386887, 16012798675095097, 128102389400760775, 1024819115206086201, 8198552921648689607

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

A linear 2nd order recurrence. A Jacobsthal number sequence.

Binomial transform of A053573 (preceded by zero). - Paul Barry, Apr 09 2003

Second binomial transform of A080424. Binomial transform of A053573, with leading zero. Binomial transform is 0,1,9,81,729,....(9^n - 0^n)/9. Second binomial transform is 0,1,11,111,1111,... (A002275: repunits). - Paul Barry, Mar 14 2004

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

Unsigned version of A014990. - Philippe Deléham, Feb 13 2007

General form: k=8^n-k. Also: A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499, A015531, A109500, A109501, A015552. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

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

Examples

			G.f. = x + 7*x^2 + 57*x^3 + 455*x^4 + 3641*x^5 + 29127*x^6 + 233017*x^7 + ...
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, and Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
• M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
• Dale Gerdemann, Fractal generated from (7,8) recursion, YouTube Video, Dec 5, 2014.
• Index entries for linear recurrences with constant coefficients, signature (7,8).

Crossrefs

Cf. A002275, A014990, A053573, A080424, A082311, A082365.

Cf. A062160, A099322, A106566.

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

Programs

Magma

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

Maple

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

Mathematica

k=0;lst={k};Do[k=8^n-k;AppendTo[lst, k], {n, 0, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008 *)
LinearRecurrence[{7,8},{0,1},30] (* Harvey P. Dale, Mar 04 2016 *)

PARI

x='x+O('x^30); concat([0], Vec(x/(1-7*x-8*x^2))) \\ G. C. Greubel, Dec 30 2017

Sage

[lucas_number1(n,7,-8) for n in range(0, 21)] # Zerinvary Lajos, Apr 24 2009

Formula

From Paul Barry, Apr 09 2003: (Start)

a(n) = (8^n - (-1)^n)/9.

a(n) = J(3*n)/3 = A001045(3*n)/3. (End)

From Emeric Deutsch, Apr 01 2004: (Start)

a(n) = 8^(n-1) - a(n-1).

G.f.: x/(1-7*x-8*x^2). (End)

a(n) = Sum_{k = 0..n} A106566(n,k)*A099322(k). - Philippe Deléham, Oct 30 2008

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

From Peter Bala, May 31 2024: (Start)

G.f: A(x) = x/(1 - x^2) o x/(1 - x^2), where o denotes the black diamond product of power series as defined by Dukes and White. Cf. A054878.

The black diamond product A(x) o A(x) is the g.f. for the number of walks of length n between any two distinct nodes of the complete graph K_81.

Row 8 of A062160. (End)

E.g.f.: exp(-x)*(exp(9*x) - 1)/9. - Elmo R. Oliveira, Aug 17 2024