A206776 a(n) = 3*a(n-1) + 2*a(n-2) for n>1, a(0)=2, a(1)=3.

2, 3, 13, 45, 161, 573, 2041, 7269, 25889, 92205, 328393, 1169589, 4165553, 14835837, 52838617, 188187525, 670239809, 2387094477, 8501763049, 30279478101, 107841960401, 384084837405, 1367938433017, 4871984973861, 17351831787617, 61799465310573

Offset: 0

Author

Bruno Berselli, Jan 10 2013

Keywords

• nonn
• easy

Comments

This is the Lucas sequence V(3,-2).

Inverse binomial transform of this sequence is A072265.

a(n) = A124805(n) - 1 for n>0.

Examples

			G.f. = 2 + 3*x + 13*x^2 + 45*x^3 + 161*x^4 + 573*x^5 + 2041*x^6 + 7269*x^7 + ...
		

References

• Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Exercise 7.49(c), pages 379, 573.

Links

• Bruno Berselli, Table of n, a(n) for n = 0..200
• Wikipedia, Lucas sequence: Specific names.
• Index entries for linear recurrences with constant coefficients, signature (3,2).

Crossrefs

Cf. A189736 (same recurrence but with initial values reversed).

Cf. A007482, A072265, A124805.

Programs

Magma

[n le 1 select n+2 else 3*Self(n)+2*Self(n-1): n in [0..25]];

Maple

A206776 := proc(n)
    option remember ;
    if n <= 1 then
        n+2 ;
    else
        3*procname(n-1)+2*procname(n-2) ;
    end if;
end proc:
seq(A206776(n),n=0..30) ; # R. J. Mathar, Feb 18 2024

Mathematica

RecurrenceTable[{a[n] == 3 a[n - 1] + 2 a[n - 2], a[0] == 2, a[1] == 3}, a[n], {n, 25}]
LinearRecurrence[{3,2},{2,3},30] (* Harvey P. Dale, Apr 29 2014 *)
a[ n_] := If[ n < 0, (-2)^n a[ -n], ((3 + Sqrt[17])/2)^n + ((3 - Sqrt[17])/2)^n // Expand]; (* Michael Somos, Oct 13 2016 *)
a[ n_] := If[ n < 0, (-2)^n a[ -n], Boole[n == 0] + SeriesCoefficient[ ((1 + 3*x + Sqrt[1 + 6*x + 17*x^2])/2)^n, {x, 0, n}]]; (* Michael Somos, Oct 13 2016 *)

Maxima

a[0]:2$ a[1]:3$ a[n]:=3*a[n-1]+2*a[n-2]$ makelist(a[n], n, 0, 25);

PARI

Vec((2-3*x)/(1-3*x-2*x^2) + O(x^30)) \\ Michel Marcus, Jun 26 2015

PARI

{a(n) = 2 * real(( (3 + quadgen(68)) / 2 )^n)}; /* Michael Somos, Oct 13 2016 */

PARI

{a(n) = my(w = quadgen(-8)); simplify(w^n * subst(2 * polchebyshev(n), x, -3/4*w))}; /* Michael Somos, Oct 13 2016 */

PARI

for(n=0,25,print1(round(((3+sqrt(17))/2)^n+((3-sqrt(17))/2)^n),", ")) \\ Hugo Pfoertner, Nov 19 2018

Formula

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

a(n) = ((3-sqrt(17))^n+(3+sqrt(17))^n)/2^n.

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

a(n) = (-2)^n * a(-n) for all n in Z. - Michael Somos, Oct 13 2016

If c = (3 + sqrt(17))/2, then c^n = (a(n) + sqrt(17)*A007482(n-1)) / 2. - Michael Somos, Oct 13 2016

E.g.f.: 2*exp(3*x/2)*cosh(sqrt(17)*x/2). - Stefano Spezia, Oct 21 2022

a(n) = 2*A007482(n)-3*A007482(n-1). - R. J. Mathar, Feb 18 2024