A084707 a(n) = 3*a(n-1) - 3*a(n-3) + a(n-4) for n > 3, with a(0) = 1, a(1) = 3, a(2) = 9, a(3) = 27.

1, 3, 9, 27, 73, 195, 513, 1347, 3529, 9243, 24201, 63363, 165889, 434307, 1137033, 2976795, 7793353, 20403267, 53416449, 139846083, 366121801, 958519323, 2509436169, 6569789187, 17199931393, 45030004995, 117890083593, 308640245787, 808030653769

Offset: 0

Author

N. J. A. Sloane, Jul 06 2003

Keywords

• nonn
• easy

Comments

Define f(x, y) := 9 - x - 3*y + x^2 - 3*x*y + y^2. Then f(x, y) = f(-4-y, -4-x). All of the integer solutions of 0 = f(x, y) with x>=0 are given by x = a(2*n) and y = a(2*n+1) for all n in Z. - Michael Somos, Aug 19 2023

Examples

			G.f. = 1 + 3*x + 9*x^2 + 27*x^3 + 73*x^4 + 195*x^5 + 513*x^6 + ... - _Michael Somos_, Aug 19 2023
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• J. Hietarinta and C.-M. Viallet, Singularity confinement and chaos in discrete systems, Physical Review Letters 81 (1998), pp. 326-328.
• Index entries for linear recurrences with constant coefficients, signature (3,0,-3,1).

Crossrefs

Cf. A005248, A069403.

Programs

Magma

A084707:=[1,3,9,27]; [n le 4 select A084707[n] else 3*Self(n-1)-3*Self(n-3)+Self(n-4): n in [1..30]]; // Wesley Ivan Hurt, Aug 15 2016

Magma

[(8*Lucas(2*n) -(-1)^n)/5 -2: n in [0..40]]; // G. C. Greubel, Apr 15 2023

Maple

a:=proc(n) option remember; if n=0 then 1 elif n=1 then 3 elif n=2 then 9 elif n=3 then 27 else 3*a(n-1)-3*a(n-3)+a(n-4); fi; end: seq(a(n), n=0..40); # Wesley Ivan Hurt, Aug 15 2016

Mathematica

a[n_]:=a[n]=3a[n-1] -3a[n-3] +a[n-4]; a[0]=1; a[1]=3; a[2]=9; a[3]=27;
Table[ a[n], {n, 0, 27}]
Transpose[NestList[Join[Rest[#],ListCorrelate[{1,-3,0,3},#]]&, {1,3,9,27},30]][[1]]
CoefficientList[Series[(1+3 x^3)/(1-3 x+3 x^3-x^4),{x,0,30}],x]  (* Harvey P. Dale, Mar 14 2011 *)
a[ n_] := Floor[(LucasL[2*n] - 1)*8/5]; (* Michael Somos, Aug 19 2023 *)

PARI

{a(n) = my(w=quadgen(5)); (real((1+w)^n*(2+w))-1)*8\5}; /* Michael Somos, Aug 19 2023 */

SageMath

[(8*lucas_number2(2*n,1,-1) -(-1)^n)/5 -2 for n in range(41)] # G. C. Greubel, Apr 15 2023

Formula

G.f.: (1+3*x^3)/(1-3*x+3*x^3-x^4). - Harvey P. Dale, Mar 14 2011

a(n) = (8*LucasL(2*n) - (-1)^n - 10)/5. - G. C. Greubel, Apr 15 2023

a(n) = a(-n) = 4 + 2*a(n-1) + 2*a(n-2) - a(n-3) for all n in Z. - Michael Somos, Aug 19 2023

Extensions

More terms from Ray Chandler, Jul 07 2003