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

Offset

0,3

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

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.

Dale Gerdemann, Fractal generated from (7,8) recursion, YouTube Video, Dec 5, 2014

Index entries for linear recurrences with constant coefficients, signature (7,8).

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<=k<=n} A106566(n,k)*A099322(k). - Philippe Deléham, Oct 30 2008

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

Example

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

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 *)

Prog

(Sage) [lucas_number1(n, 7, -8) for n in range(0, 21)] # Zerinvary Lajos, Apr 24 2009
(Magma) [Round(8^n/9): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011
(PARI) x='x+O('x^30); concat([0], Vec(x/(1-7*x-8*x^2))) \\ G. C. Greubel, Dec 30 2017

Crossrefs

Cf. A082311, A082365.

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

Sequence in context: A218838 A082310 A014990 * A349303 A268316 A291537

Adjacent sequences: A015562 A015563 A015564 * A015566 A015567 A015568

Keyword

nonn,easy

Author

Olivier Gérard

Status

approved