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

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

Author

Gary W. Adamson, Dec 23 2004

Keywords

• nonn
• easy

Comments

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

Examples

			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.
		

Links

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

Crossrefs

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

Programs

GAP

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

Magma

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

Maple

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

Mathematica

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

PARI

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

PARI

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

Sage

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

Formula

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)

Extensions

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