A001019 -id:A001019 - cp's OEIS frontend

A339689 a(n) = Sum_{d|n} 9^(d-1).

1, 10, 82, 739, 6562, 59140, 531442, 4783708, 43046803, 387427060, 3486784402, 31381119478, 282429536482, 2541866359780, 22876792461604, 205891136878357, 1853020188851842, 16677181742772430, 150094635296999122, 1350851718060419878, 12157665459057460324

Offset: 1

Ilya Gutkovskiy, Dec 12 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1000

Column 9 of A308813.
Cf. A001019, A320074.
Sums of the form Sum_{d|n} q^(d-1): A034729 (q=2), A034730 (q=3), A113999 (q=10), A339684 (q=4), A339685 (q=5), A339686 (q=6), A339687 (q=7), A339688 (q=8), this sequence (q=9).

A339689:= func< n | (&+[9^(d-1): d in Divisors(n)]) >;
[A339689(n): n in [1..40]]; // G. C. Greubel, Jun 25 2024

Table[Sum[9^(d - 1), {d, Divisors[n]}], {n, 1, 21}]
nmax = 21; CoefficientList[Series[Sum[x^k/(1 - 9 x^k), {k, 1, nmax}], {x, 0, nmax}], x] // Rest

a(n) = sumdiv(n, d, 9^(d-1)); \\ Michel Marcus, Dec 13 2020

def A339689(n): return sum(9^(k-1) for k in (1..n) if (k).divides(n))
[A339689(n) for n in range(1,41)] # G. C. Greubel, Jun 25 2024

G.f.: Sum_{k>=1} x^k / (1 - 9*x^k).
G.f.: Sum_{k>=1} 9^(k-1) * x^k / (1 - x^k).
a(n) ~ 9^(n-1). - Vaclav Kotesovec, Jun 05 2021

A085363 a(0)=1, for n>0: a(n) = 49^(n-1) - (1/2)Sum_{i=1..n-1} a(i)*a(n-i).

Original entry on oeis.org

1, 4, 28, 212, 1676, 13604, 112380, 940020, 7936620, 67494980, 577309148, 4961187092, 42801458764, 370478720356, 3215827927228, 27982214082612, 244004165618220, 2131710838837380, 18654504783815580, 163488269572628820

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Jun 25 2003

Apparently, the number of 2-D directed walks of semilength n starting at (0,0) and ending on the X-axis using steps NE, SE, NW and SW avoiding adjacent NW/SE and adjacent NE/SW. - David Scambler, Jun 20 2013
Form an array with m(0,n) = m(n,0) = 2^n; m(i,j) equals the sum of the terms to the left of m(i,j) and the sum of the terms above m(i,j), which is m(i,j) = Sum_{k-0..j-1} m(i,k) + Sum_{k=0..i-1} m(k,j).  m(n,n) = a(n). - J. M. Bergot, Jul 10 2013
From G. C. Greubel, May 22 2020: (Start)
This sequence is part of a class of sequences, for m >= 0, with the properties:
a(n) = 2*m*(4*m+1)^(n-1) - (1/2)*Sum_{k=1..n-1} a(k)*a(n-k).
a(n) = Sum_{k=0..n} m^k * binomial(n-1, n-k) * binomial(2*k, k).
a(n) = (2*m) * Hypergeometric2F1(-n+1, 3/2; 2; -4*m), for n > 0.
n*a(n) = 2*((2*m+1)*n - (m+1))*a(n-1) - (4*m+1)*(n-2)*a(n-2).
(4*m + 1)^n = Sum_{k=0..n} Sum_{j=0..k} a(j)*a(k-j).
G.f.: sqrt( (1 - t)/(1 - (4*m+1)*t) ).
This sequence is the case of m=2. (End)
The number of elements in the free group on two generators of length 2n that are zero exponent sum. - Tey Berendschot, Aug 09 2021

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Kees A.S. Immink and Kui Cai, Properties and constructions of constrained codes for DNA-based data storage, IEEE Access, vol. 8, no. 1, pp. 49523-49531, 2020, page 49529.
John Machacek, Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats, preprint arXiv:2105.02417 [math.CO], 2021.

Cf. A001019 (9^n), A084771, A085362, A085364, diagonal of A348595.

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( Sqrt((1-x)/(1-9*x)) )); // G. C. Greubel, May 23 2020

seq(coeff(series(sqrt((1-x)/(1-9*x)), x, n+1), x, n), n = 0..30); # G. C. Greubel, May 23 2020

CoefficientList[Series[Sqrt[(1-x)/(1-9x)], {x, 0, 25}], x]

my(x='x+O('x^66)); Vec(sqrt((1-x)/(1-9*x)) ) \\ Joerg Arndt, May 10 2013

def A085363_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( sqrt((1-x)/(1-9*x)) ).list()
A085363_list(30) # G. C. Greubel, May 23 2020

G.f.: sqrt((1-x)/(1-9*x)).
Sum_{i=0..n} Sum_{j=0..i} a(j)*a(i-j) = 9^n.
From Vladeta Jovovic, Oct 10 2003: (Start)
First differences of A084771.
a(n) = Sum_{k=1..n} 2^k * binomial(n-1, k-1) * binomial(2*k, k). (End)
D-finite with recurrence n*a(n) = (10*n-6)*a(n-1) - (9*n-18)*a(n-2). - Vladeta Jovovic, Jul 16 2004
a(n) ~ 2*sqrt(2)*3^(2*n-1)/sqrt(Pi*n). - Vaclav Kotesovec, Oct 14 2012
a(0) = 1; a(n) = (4/n) * Sum_{k=0..n-1} (n+k) * a(k). - Seiichi Manyama, Mar 28 2023
From Seiichi Manyama, Aug 22 2025: (Start)
a(n) = (1/4)^n * Sum_{k=0..n} 9^k * binomial(2*k,k) * binomial(2*(n-k),n-k)/(1-2*(n-k)).
a(n) = Sum_{k=0..n} (-2)^k * 9^(n-k) * binomial(2*k,k)/(1-2*k) * binomial(n-1,n-k). (End)

A101990 a(1) = a(2) = 1, a(3) = 9; for n > 3, a(n) = 3a(n-1) - 3a(n-2) + 9*a(n-3).

Original entry on oeis.org

1, 1, 9, 33, 81, 225, 729, 2241, 6561, 19521, 59049, 177633, 531441, 1592865, 4782969, 14353281, 43046721, 129127041, 387420489, 1162300833, 3486784401, 10460235105, 31381059609, 94143533121, 282429536481, 847287546561, 2541865828329, 7625600673633

Offset: 1

Gary W. Adamson, Dec 23 2004

Alternate terms are powers of 9 (A001019): a(2b+1) = 9^b; b = 0, 1, 2, ...

a(n) is the number of solutions to Sum_{i=1..n} x_i^2 == 0 (mod 3) for (x_1, x_2, ..., x_n). - Jianing Song, Jul 03 2018

			a(5) = 81 since M^5 * [1 0 0]^T = [81 90 72]^T.
a(5) = 81 = 99 - 27 + 9 = 3*33 - 3*9 + 9*1 = 3*a(4) - 3*a(3) + 9*a(2).
a(7) = 729 = 9^3. (let b = 3, then n = 2b+1 = 7; and a(2b+1) = 9^b.

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-3,9).

A318609 gives the number of solutions to Sum_{i=1..n} x_i^2 == 1 (mod 3);

A318610 gives the number of solutions to Sum_{i=1..n} x_i^2 == 2 (mod 3).

a:=[1,1,9];; for n in [4..30] do a[n]:=3*a[n-1]-3*a[n-2]+9*a[n-3]; od; a; # G. C. Greubel, Dec 20 2019

a:=[1,1,9]; [n le 3 select a[n] else 3*Self(n-1)-3*Self(n-2) + 9*Self(n-3):n in [1..30]]; // Marius A. Burtea, Dec 20 2019

seq(`if`( `mod`(n,2)=1, 3^(n-1), 3^(n-1)-2*(-3)^(n/2 -1) ), n = 0..30); # G. C. Greubel, Dec 20 2019

a[n_]:= a[n]= 3a[n-1] - 3a[n-2] + 9a[n-3]; a[1]= a[2]= 1; a[3]= 9; Table[ a[n], {n, 26}] (* Or *)
a[n_] := (MatrixPower[{{1, 0, 2}, {2, 1, 0}, {0, 2, 1}}, n].{{1}, {0}, {0}})[[1, 1]]; Table[ a[n], {n, 26}] (* Robert G. Wilson v, Dec 23 2004 *)

Vec(x*(1-2*x+9*x^2)/((1-3*x)*(1+3*x^2)) + O(x^40)) \\ Colin Barker, Sep 23 2016

a(n) = ([1, 0, 2 ; 2, 1, 0 ; 0, 2, 1]^n*mattranspose([1, 0, 0]))[1]; \\ Michel Marcus, Dec 20 2019

def A101990_list(n) :
    f = (exp(3*x/2)+2*cos(sqrt(3)*x/2))/3
    s = f.series(x,n+2)
    return [(2^i*factorial(i)*s.coefficient(x,i)) for i in (1..n)]
A101990_list(26)  # Peter Luschny, Aug 01 2012

a(n) = first term in M^n * [1 0 0]^T, where M = the 3 X 3 matrix [1 0 2 / 2 1 0 / 0 2 1] and T denotes transpose. [Edited by Michel Marcus, Dec 20 2019]
G.f.: x*(1 - 2*x + 9*x^2)/((1 - 3*x)*(1 + 3*x^2)). - R. J. Mathar, Aug 22 2008
a(n) = 2^n*n!*[x^n] (exp(3*x/2) + 2*cos(sqrt(3)*x/2))/3. - Peter Luschny, Aug 01 2012
a(n) = 3^(n/2 - 1)*((-i)^n + i^n + 3^(n/2)) where i = sqrt(-1). - Colin Barker, Sep 23 2016
From Jianing Song, Sep 05 2018: (Start)
E.g.f.: 1/3*(exp(3*x) + 2*cos(sqrt(3)*x)) (with a(0) = 1 prepended).
a(n) = 3^(n/2 - 1)*(2*cos(n*Pi/2) + 3^(n/2)).
a(n) = 3^(n-1) for odd n and 3^(n-1) - 2*(-3)^(n/2-1) for even n.
a(n) = a(n-1) + 2*A318610(n-1).
a(n) + A318609(n) + A318610(n) = 3^n.
(End)

Edited and extended by Robert G. Wilson v, Dec 23 2004

A135779 Numbers having number of divisors equal to number of digits in base 9.

Original entry on oeis.org

1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 121, 169, 289, 361, 529, 731, 734, 737, 745, 746, 749, 753, 755, 758, 763, 766, 767, 771, 778, 779, 781, 785, 789, 791, 793, 794, 799, 802, 803, 807, 813, 815, 817

Offset: 1

M. F. Hasler, Nov 28 2007

Since 9 is not a prime, no element > 1 of the sequence A001019(k)=9^k (having k+1 digits in base 9, but 2k+1 divisors) can be member of this sequence. Also, no power of a prime less than 9 can be in the sequence, since it will always have fewer divisors than digits in base 9. However all powers of 11 up to 11^10 are in this sequence, having the same number of digits (in base 9) than the same power of 9 (since 10 = floor(log(11/9)/log(9))) and also that number of divisors (since 11 is prime).

			a(1) = 1 since 1 has 1 divisor and 1 digit (in base 9 as in any other base).
It is followed by the primes (having 2 divisors {1,p}) between 9 and 9^2 - 1 (to have 2 digits in base 9).
Then come the squares of primes (3 divisors) between 9^2 = 100_9 and 9^3 - 1 = 888_9.
These are followed by all semiprimes and cubes of primes (4 divisors) between 9^3 and 9^4 - 1.

G. C. Greubel, Table of n, a(n) for n = 1..1500

Cf. A135772-A135778, A095862.

Select[Range[500], DivisorSigma[0, #] == IntegerLength[#, 9] &] (* G. C. Greubel, Nov 09 2016 *)

for(d=1,4,for(n=9^(d-1),9^d-1,d==numdiv(n)&print1(n", ")))

A165830 Totally multiplicative sequence with a(p) = 9.

Original entry on oeis.org

1, 9, 9, 81, 9, 81, 9, 729, 81, 81, 9, 729, 9, 81, 81, 6561, 9, 729, 9, 729, 81, 81, 9, 6561, 81, 81, 729, 729, 9, 729, 9, 59049, 81, 81, 81, 6561, 9, 81, 81, 6561, 9, 729, 9, 729, 729, 81, 9, 59049, 81, 729

Offset: 1

Jaroslav Krizek, Sep 28 2009

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A001019, A001222.

9^PrimeOmega[Range[100]] (* G. C. Greubel, Apr 09 2016 *)

a(n) = 9^bigomega(n); \\ Altug Alkan, Apr 09 2016

a(n) = A001019(A001222(n)) = 9^bigomega(n) = 9^A001222(n).

Dirichlet g.f.: Product_{p prime} 1 / (1 - 9 * p^(-s)). - Ilya Gutkovskiy, Oct 30 2019

A212703 Main transitions in systems of n particles with spin 4.

Original entry on oeis.org

8, 144, 1944, 23328, 262440, 2834352, 29760696, 306110016, 3099363912, 30993639120, 306837027288, 3012581722464, 29372671794024, 284688972772848, 2745215094595320, 26354064908115072, 252010745683850376, 2401514164751985936, 22814384565143866392, 216136274827678734240

Offset: 1

Stanislav Sykora, May 25 2012

Please, refer to the general explanation in A212697.

This sequence is for base b=9 (see formula), corresponding to spin S=(b-1)/2=4.

Stanislav Sykora, Table of n, a(n) for n = 1..100
Stanislav Sýkora, Magnetic Resonance on OEIS, Stan's NMR Blog (Dec 31, 2014), Retrieved Nov 12, 2019.
Index entries for linear recurrences with constant coefficients, signature (18,-81).

Cf. A001787, A212697, A212698, A212699, A212700, A212701, A212702, A212704 (b = 2, 3, 4, 5, 6, 7, 8, 10).

Cf. A001019, A008590, A053540.

LinearRecurrence[{18,-81},{8,144},30] (* Harvey P. Dale, Jun 28 2017 *)

mtrans(n, b) = n*(b-1)*b^(n-1);
for (n=1, 100, write("b212703.txt", n, " ", mtrans(n, 9)))

Vec(8*x/(9*x-1)^2 + O(x^100)) \\ Colin Barker, Jun 16 2015

a(n)=8*n*9^(n-1) \\ Charles R Greathouse IV, Jun 16 2015

a(n) = n*(b-1)*b^(n-1). For this sequence, set b=9.
From Colin Barker, Jun 16 2015: (Start)
a(n) = 18*a(n-1) - 81*a(n-2) for n > 2.
G.f.: 8*x/(9*x-1)^2. (End)
From Elmo R. Oliveira, May 13 2025: (Start)
E.g.f.: 8*x*exp(9*x).
a(n) = 8*A053540(n) = A008590(n)*A001019(n-1). (End)

A010690 Period 2: repeat (1,9).

Original entry on oeis.org

1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9, 1

Offset: 0

N. J. A. Sloane

Digital roots of the nonzero square triangular numbers. - Ant King, Jan 21 2012
Continued fraction expansion of A176019. - R. J. Mathar, Mar 08 2012
Exp( Sum_{n >= 1} a(n-1)*x^n/n ) = 1 + x + 5*x^2 + 5*x^3 + 15*x^4 + 15*x^5 + ... is the o.g.f. for A189976 (taken with an offset of 0). - Peter Bala, Mar 13 2015
Final digit of 9^n. - Martin Renner, Jun 11 2020
Decimal expansion of 19/99. - Stefano Spezia, Feb 09 2025

			0.191919191919191919191919191919191919191...

Index entries for linear recurrences with constant coefficients, signature (0,1).

Cf. A008592, A001019 (9^n), A014393, A189976.

5+4*(-1)^# &/@Range[81] (* Ant King, Jan 21 2012 *)

a(n)=1; if(n%2==1, 9, 1) \\ Felix Fröhlich, Aug 11 2014

G.f.: (1+9x)/((1-x)(1+x)). - R. J. Mathar, Nov 21 2011
a(n) = 9^n mod 10. - Martin Renner, Jun 11 2020
E.g.f.: cosh(x) + 9*sinh(x). - Stefano Spezia, Feb 09 2025
From Amiram Eldar, Jun 09 2025: (Start)
With offset 1:
Multiplicative with a(2^e) = 9, a(p^e) = 1 for an odd prime p.
Dirichlet g.f.: zeta(s) * (1 + 1/2^(s-3)). (End)

A128969 a(n) = (n^3 - n)*9^n.

Original entry on oeis.org

0, 486, 17496, 393660, 7085880, 111602610, 1607077584, 21695547384, 278942752080, 3451916556990, 41422998683880, 484649084601396, 5551434969070536, 62453643402043530, 691794203838020640, 7560322370515511280, 81651481601567521824, 872650209616752889494

Offset: 1

Mohammad K. Azarian, Apr 28 2007

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (36,-486,2916,-6561).

Cf. A001019, A007531, A036289, A038291, A128796.

Cf. A128960, A128961, A128962, A128963, A128964, A128965, A128967.

[(n^3-n)*9^n: n in [0..25]]; // Vincenzo Librandi, Feb 11 2013

I:=[0, 486, 17496, 393660]; [n le 4 select I[n] else 36*Self(n-1) - 486*Self(n-2) + 2916*Self(n-3) - 6561*Self(n-4): n in [1..25]]; // Vincenzo Librandi, Feb 11 2013

CoefficientList[Series[486 x/(1 - 9 x)^4, {x, 0, 30}], x] (* Vincenzo Librandi, Feb 11 2013 *)

From R. J. Mathar, Dec 19 2008 (Start)
G.f.: 486x^2/(1-9x)^4.
a(n) = 486*A038291(n+1,3). (End)
a(n) = 36*a(n-1) - 486*a(n-2) + 2916*a(n-3) - 6561*a(n-4). - Vincenzo Librandi, Feb 11 2013
From Amiram Eldar, Oct 02 2022: (Start)
a(n) = A007531(n+1)*A001019(n).
Sum_{n>=2} 1/a(n) = (32/9)*log(9/8) - 5/12.
Sum_{n>=2} (-1)^n/a(n) = (50/9)*log(10/9) - 7/12. (End)

Offset corrected by Mohammad K. Azarian, Nov 20 2008

A173000 a(n) = binomial(n + 4, 4)*9^n.

Original entry on oeis.org

1, 45, 1215, 25515, 459270, 7440174, 111602610, 1578379770, 21308126895, 277005649635, 3490271185401, 42835146366285, 514021756395420, 6049640671423020, 70002984912180660, 798034027998859524, 8977882814987169645, 99812932472504415465, 1097942257197548570115

Offset: 0

Zerinvary Lajos, Feb 07 2010

Number of n-permutations (n>=4) of 10 objects p, r, q, u, v, w, z, x, y, z with repetition allowed, containing exactly 4 u's.

Vincenzo Librandi, Table of n, a(n) for n = 0..400
Index entries for linear recurrences with constant coefficients, signature (45,-810,7290,-32805,59049).

Cf. A000332, A001019.

[Binomial(n+4, 4)*9^n: n in [0..20]]; // Vincenzo Librandi, Oct 13 2011

A173000:=n->binomial(n+4,4)*9^n: seq(A173000(n), n=0..25); # Wesley Ivan Hurt, Jul 24 2017

Table[Binomial[n + 4, 4]*9^n, {n, 0, 20}]

a(n)=binomial(n+4,4)*9^n \\ Charles R Greathouse IV, Oct 07 2015

G.f.: 1/(1-9*x)^5. - R. J. Mathar, Dec 21 2011
a(n) = 45*a(n-1)-810*a(n-2)+7290*a(n-3)-32805*a(n-4)+59049*a(n-5). - Wesley Ivan Hurt, Apr 21 2021
From Amiram Eldar, Aug 28 2022: (Start)
Sum_{n>=0} 1/a(n) = 2172 - 18432*log(9/8).
Sum_{n>=0} (-1)^n/a(n) = 36000*log(10/9) - 3792. (End)
a(n) = A000332(n+4)*A001019(n). - Michel Marcus, Aug 28 2022

A203656 T(n,k)=1/25 the number of (n+1)X(k+1) 0..4 arrays with every 2X2 subblock having equal diagonal elements or equal antidiagonal elements.

Original entry on oeis.org

9, 81, 81, 729, 1517, 729, 6561, 28057, 28057, 6561, 59049, 519445, 1116249, 519445, 59049, 531441, 9616161, 44577561, 44577561, 9616161, 531441, 4782969, 178019197, 1780968921, 3906948333, 1780968921, 178019197, 4782969, 43046721, 3295578857

Offset: 1

R. H. Hardin Jan 04 2012

Table starts
........9..........81.............729...............6561.................59049
.......81........1517...........28057.............519445...............9616161
......729.......28057.........1116249...........44577561............1780968921
.....6561......519445........44577561.........3906948333..........343812029649
....59049.....9616161......1780968921.......343812029649........67213191427593
...531441...178019197.....71156938905.....30292030417413.....13192335511091073
..4782969..3295578857...2843024036697...2669260624372937...2592476403527692089
.43046721.61009378085.113591039131161.235230466316286557.509649251749126118193

			Some solutions for n=4 k=3
..1..1..1..0....2..4..1..4....3..1..1..3....3..0..4..4....0..3..4..0
..4..1..2..1....2..2..4..4....4..3..1..1....2..3..0..4....3..2..3..4
..0..4..1..4....1..2..2..4....3..1..0..1....4..2..3..0....2..2..2..3
..3..0..4..3....3..1..2..2....1..1..1..0....0..4..2..3....4..2..4..2
..4..3..0..4....2..3..1..2....4..1..1..1....0..0..4..2....2..4..3..4

R. H. Hardin, Table of n, a(n) for n = 1..112

Column 1 is A001019

cp's OEIS Frontend

A339689 a(n) = Sum_{d|n} 9^(d-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A085363 a(0)=1, for n>0: a(n) = 4*9^(n-1) - (1/2)*Sum_{i=1..n-1} a(i)*a(n-i).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A101990 a(1) = a(2) = 1, a(3) = 9; for n > 3, a(n) = 3*a(n-1) - 3*a(n-2) + 9*a(n-3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A135779 Numbers having number of divisors equal to number of digits in base 9.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A165830 Totally multiplicative sequence with a(p) = 9.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A212703 Main transitions in systems of n particles with spin 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A010690 Period 2: repeat (1,9).

A085363 a(0)=1, for n>0: a(n) = 49^(n-1) - (1/2)Sum_{i=1..n-1} a(i)*a(n-i).

A101990 a(1) = a(2) = 1, a(3) = 9; for n > 3, a(n) = 3a(n-1) - 3a(n-2) + 9*a(n-3).