A007484 a(n) = 3*a(n-1) + 2*a(n-2), with a(0)=2, a(1)=7.

2, 7, 25, 89, 317, 1129, 4021, 14321, 51005, 181657, 646981, 2304257, 8206733, 29228713, 104099605, 370756241, 1320467933, 4702916281, 16749684709, 59654886689, 212464029485, 756701861833, 2695033644469, 9598504657073, 34185581260157, 121753753094617, 433632421804165

Offset: 0

Author

N. J. A. Sloane

Keywords

• easy
• nonn
• nice

Comments

Number of subsequences of [1,...,2n+1] in which each even number has an odd neighbor.

Same as Pisot sequence E(2,7) (see A008776).

8*a(n) = A007482(n+2) + A007483(n+1) (conjectured, see A104934 for related formula). - Creighton Dement, Apr 15 2005

Conjecture verified using generating functions. - Robert Israel, Jul 12 2018

a(n) = sum of the elements of the matrix M^n, where M = {{1, 2}, {2, 2}}. - Griffin N. Macris, Mar 25 2016

a(3) = 25 is the only composite among the first 8 terms, but then the density of primes decreases, dropping below 50% at the 27th term. - M. F. Hasler, Jul 12 2018

a(n) is also the number of dominating sets in the (2n+1)-triangular snake graph for n > 0. - Eric W. Weisstein, Jun 09 2019

Examples

			G.f. = 2 + 7*x + 25*x^2 + 89*x^3 + 317*x^4 + 1129*x^5 + ... - _Michael Somos_, Jul 19 2021
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• R. K. Guy and W. O. J. Moser, Numbers of subsequences without isolated odd members, Fibonacci Quarterly 34:2 (1996), pp. 152-155.
• Eric Weisstein's World of Mathematics, Dominating Set
• Eric Weisstein's World of Mathematics, Triangular Snake Graph
• Index entries for linear recurrences with constant coefficients, signature (3,2).

Crossrefs

Cf. A007455, A007481, A007483, A007484, A104934.

See A008776 for definitions of Pisot sequences.

Programs

Haskell

a007484 n = a007484_list !! n
a007484_list = 2 : 7 : zipWith (+)
               (map (* 3) $ tail a007484_list) (map (* 2) a007484_list)
-- Reinhard Zumkeller, Nov 02 2015

Magma

A007484:=[2, 7]; [n le 2 select A007484[n] else 3*Self(n-1)+2*Self(n-2): n in [1..40]]; // Wesley Ivan Hurt, Jan 24 2017

Maple

A007484 := proc(n) option remember; if n=0 then 2; elif n=1 then 7; else 3*A007484(n-1)+2*A007484(n-2); fi; end;

Mathematica

LinearRecurrence[{3, 2}, {2, 7}, 40] (* Harvey P. Dale, Apr 24 2012 *)
Table[(2^-n ((3 - Sqrt[17])^n (-4 + Sqrt[17]) + (3 + Sqrt[17])^n (4 + Sqrt[17])))/Sqrt[17], {n, 0, 20}] // Expand (* Eric W. Weisstein, Jun 09 2019 *)
CoefficientList[Series[(2+x)/(1 -3x -2x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 09 2019 *)
a[ n_] := MatrixPower[{{1, 2}, {2, 2}}, n]//Flatten//Total; (* Michael Somos, Jul 19 2021 *)

PARI

a(n)=([0,1; 2,3]^n*[2;7])[1,1] \\ Charles R Greathouse IV, Mar 25 2016

PARI

A007484_vec(N)=Vec((2+x)/(1-3*x-2*x^2)+O(x^n)) \\ M. F. Hasler, Jul 12 2018

Sage

[(i*sqrt(2))^(n-1)*( i*2*sqrt(2)*chebyshev_U(n, -3*i/(2*sqrt(2))) + chebyshev_U(n-1, -3*i/(2*sqrt(2))) ) for n in (0..30)] # G. C. Greubel, Jul 18 2021

Formula

a(n) = nearest integer to (and converges rapidly to) (1+4/sqrt(17))*((3+sqrt(17))/2)^n. - N. J. A. Sloane, Jul 30 2016

If p[i] = Fibonacci(i+2) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)= det A. - Milan Janjic, May 08 2010

G.f.: (2 + x)/(1 - 3*x - 2*x^2). - M. F. Hasler, Jul 12 2018

From G. C. Greubel, Jul 18 2021: (Start)

a(n) = (i*sqrt(2))^(n-1)*( i*2*sqrt(2)*ChebyshevU(n, -3*i/(2*sqrt(2))) + ChebyshevU(n-1, -3*i/(2*sqrt(2))) ).

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*((7*n-8*k)/(n-k))*2^k*3^(n-2*k-1) with a(0) = 2. (End)

If we extend the definition of A007483(m) to negative m by using the recurrence, then a(n) = A007483(-3-n)*(-2)^n holds for all n in Z. - Michael Somos, Jul 19 2021

E.g.f.: 2*exp(3*x/2)*(17*cosh(sqrt(17)*x/2) + 4*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, May 24 2024

Extensions

Definition edited by N. J. A. Sloane, Jul 30 2016