A075118 Variant on Lucas numbers: a(n) = a(n-1) + 3*a(n-2) with a(0)=2 and a(1)=1.

2, 1, 7, 10, 31, 61, 154, 337, 799, 1810, 4207, 9637, 22258, 51169, 117943, 271450, 625279, 1439629, 3315466, 7634353, 17580751, 40483810, 93226063, 214677493, 494355682, 1138388161, 2621455207, 6036619690, 13900985311, 32010844381, 73713800314, 169746333457

Offset: 0

Author

Henry Bottomley, Sep 02 2002

Keywords

• nonn
• easy

Comments

The sequence 4,1,7,.. = 2*0^n+A075118(n) is given by trace(A^n) where A=[1,1,1,1;1,0,0,0;1,0,0,0;1,0,0,0]. - Paul Barry, Oct 01 2004

For n>2, a(n) is the numerator of the value of the continued fraction 1+3/(1+3/(1+...+3/7)) where there are n-2 1's. - Alexander Mark, Aug 16 2020

Examples

			a(4) = a(3)+3*a(2) = 10+3*7 = 31.
		

References

• Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", Wiley, 2001, p. 471.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Wikipedia, Lucas sequence
• Index entries for linear recurrences with constant coefficients, signature (1,3).

Crossrefs

Cf. A000032, A006130, A014551, A072265, A075117, A274977.

Programs

GAP

a:=[2,1];; for n in [3..40] do a[n]:=a[n-1]+3*a[n-2]; od; a; # G. C. Greubel, Jan 15 2020

Magma

I:=[2,1]; [n le 2 select I[n] else Self(n-1)+3*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Jul 20 2013

Magma

R:=PowerSeriesRing(Integers(), 33); Coefficients(R!((2-x)/(1-x-3*x^2))); // Marius A. Burtea, Jan 15 2020

Maple

a:= n-> (Matrix([[1,2]]). Matrix([[1,1], [3,0]])^n)[1,2]:
seq(a(n), n=0..35);  # Alois P. Heinz, Aug 15 2008

Mathematica

a[0]=2; a[1]=1; a[n_]:= a[n]= a[n-1] +3a[n-2]; Table[a[n], {n, 0, 30}]
CoefficientList[Series[(2-x)/(1-x-3x^2), {x,0,40}], x] (* Vincenzo Librandi, Jul 20 2013 *)
LinearRecurrence[{1,3},{2,1},40] (* Harvey P. Dale, Jun 18 2017 *)
Table[Round[Sqrt[3]^n*LucasL[n, 1/Sqrt[3]]], {n,0,40}] (* G. C. Greubel, Jan 15 2020 *)

PARI

my(x='x+O('x^30)); Vec((2-x)/(1-x-3*x^2)) \\ G. C. Greubel, Dec 21 2017

PARI

polsym(x^2-x-3, 44) \\ Joerg Arndt, Jan 22 2023

Sage

[lucas_number2(n,1,-3) for n in range(0, 30)] # Zerinvary Lajos, Apr 30 2009

Formula

a(n) = ((1+sqrt(13))/2)^n + ((1-sqrt(13))/2)^n.

a(n) = 2*A006130(n) - A006130(n-1) = A075117(3, n).

G.f.: (2-x)/(1-x-3*x^2). - Philippe Deléham, Nov 15 2008

a(n) = [x^n] ( (1 + x + sqrt(1 + 2*x + 13*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015

a(n) = 3^(n/2) * Lucas(n, 1/sqrt(3)). - G. C. Greubel, Jan 15 2020