A180148 a(n) = 3*a(n-1) + a(n-2) with a(0)=2 and a(1)=5.

2, 5, 17, 56, 185, 611, 2018, 6665, 22013, 72704, 240125, 793079, 2619362, 8651165, 28572857, 94369736, 311682065, 1029415931, 3399929858, 11229205505, 37087546373, 122491844624, 404563080245, 1336181085359, 4413106336322, 14575500094325, 48139606619297

Offset: 0

Author

Johannes W. Meijer, Aug 13 2010

Keywords

• easy
• nonn

Comments

Inverse binomial transform of A052961 (without the leading 1).

For n >= 1, also the number of matchings in the n-alkane graph. - Eric W. Weisstein, Jul 14 2021

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Eric Weisstein's World of Mathematics, Alkane Graph
• Eric Weisstein's World of Mathematics, Matching
• Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
• Index entries for linear recurrences with constant coefficients, signature (3,1).

Crossrefs

Cf. A003688, A052906.

Appears in A180142.

Cf. A000602 (more information on n-alkanes).

Programs

Maple

a:= n-> (<<0|1>, <1|3>>^n. <<2, 5>>)[1,1]:
seq(a(n), n=0..27);  # Alois P. Heinz, Jul 14 2021

Mathematica

LinearRecurrence[{3, 1}, {5, 7}, 20] (* Eric W. Weisstein, Jul 14 2021 *)
CoefficientList[Series[(2 - x)/(1 - 3 x - x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 14 2021 *)

PARI

a(n)=([0,1;1,3]^n*[2;5])[1,1] \\ Charles R Greathouse IV, Oct 13 2016

Formula

G.f.: (2-x)/(1-3*x-x^2).

a(n) = 3*a(n-1) + a(n-2) with a(0)=2 and a(1)=5.

a(n) = ((4+7*A)*A^(-n-1) + (4+7*B)*B^(-n-1))/13 with A = (-3+sqrt(13))/2 and B = (-3-sqrt(13))/2.

Lim_{k->infinity} a(n+k)/a(k) = (-1)^n*2/(A006497(n) - A006190(n)*sqrt(13)).

a(n) = 2 * Sum_{k=0..n-2} A168561(n-2,k)*3^k + 5 * Sum_{k=0..n-1} A168561(n-1,k)*3^k, n>0. - R. J. Mathar, Feb 14 2024

a(n) = 2*A006190(n+1) - A006190(n). - R. J. Mathar, Feb 14 2024