A014916 a(1)=1, a(n) = n*4^(n-1) + a(n-1).

1, 9, 57, 313, 1593, 7737, 36409, 167481, 757305, 3378745, 14913081, 65244729, 283348537, 1222872633, 5249404473, 22429273657, 95443717689, 404681363001, 1710351420985, 7207909559865, 30297653743161, 127054676987449, 531674956009017, 2220524816272953, 9257399234039353

Offset: 1

Author

Olivier Gérard

Keywords

• nonn
• easy

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 15.
• Index entries for linear recurrences with constant coefficients, signature (9,-24,16).

Programs

Magma

I:=[1, 9]; [n le 2 select I[n] else 8*Self(n-1)-16*Self(n-2)+ 1: n in [1..30]]; // Vincenzo Librandi, Oct 23 2012

Maple

a:=n->sum (4^n-4^j, j=0..n): seq(a(n)/3, n=1..31); # Zerinvary Lajos, Dec 14 2008

Mathematica

Join[{a=1,b=9},Table[c=8*b-16*a+1;a=b;b=c,{n,60}]] (* Vladimir Joseph Stephan Orlovsky, Feb 07 2011 *)
CoefficientList[Series[1/((1 - x)(1 - 4*x)^2), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 23 2012 *)
LinearRecurrence[{9,-24,16},{1,9,57},30] (* Harvey P. Dale, Jul 25 2015 *)

Formula

a(1)=1, a(2)=9, a(n) = 8*a(n-1) - 16*a(n-2) + 1. - Vincenzo Librandi, Oct 23 2012

G.f.: x/((1-x)*(1-4*x)^2). - Vincenzo Librandi, Oct 23 2012

a(n) = (4^n*(3*n-1) + 1)/9. - Thomas M. Cowley, Jan 25 2025

E.g.f.: exp(x)*(1 + exp(3*x)*(12*x - 1))/9. - Stefano Spezia, Jan 31 2025