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,1

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

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

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

Example

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

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

Prog

(Sage) [lucas_number2(n, 1, -3) for n in range(0, 30)] # Zerinvary Lajos, Apr 30 2009
(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<x>:=PowerSeriesRing(Integers(), 33); Coefficients(R!((2-x)/(1-x-3*x^2))); // Marius A. Burtea, 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
(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

Crossrefs

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

Sequence in context: A032135 A032039 A203991 * A100245 A275320 A272931

Adjacent sequences: A075115 A075116 A075117 * A075119 A075120 A075121

Keyword

nonn,easy

Author

Henry Bottomley, Sep 02 2002

Status

approved