A007455 Number of subsequences of [ 1,...,n ] in which each odd number has an even neighbor. (Formerly M2480)

1, 1, 3, 5, 11, 17, 39, 61, 139, 217, 495, 773, 1763, 2753, 6279, 9805, 22363, 34921, 79647, 124373, 283667, 442961, 1010295, 1577629, 3598219, 5618809, 12815247, 20011685, 45642179, 71272673, 162557031, 253841389, 578955451, 904069513

Offset

0,3

References

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

Links

T. D. Noe, Table of n, a(n) for n=0..400

R. K. Guy, William O. J. Moser, Numbers of subsequences without isolated odd members, Fibonacci Quarterly, 34, No. 2, 152-155 (1996).

Index entries for linear recurrences with constant coefficients, signature (0,3,0,2).

Formula

a(n) = 3*a(n-2) + 2*a(n-4).

G.f. = (1 + x + 2 x^3)/(1 - 3 x^2 - 2 x^4). - Harvey P. Dale, Feb 18 2011, edited by M. F. Hasler, Jun 19 2019

Mathematica

CoefficientList[Series[(-1-x-2 x^3)/(-1+3 x^2+2 x^4), {x, 0, 40}], x]  (* Harvey P. Dale, Feb 18 2011 *)
LinearRecurrence[{0, 3, 0, 2}, {1, 1, 3, 5}, 40] (* Harvey P. Dale, Feb 10 2015 *)

Prog

(Haskell)
a007455_list = 1 : 1 : 3 : 5 : zipWith (+)
   (map (* 2) a007455_list) (map (* 3) $ drop 2 a007455_list)
a007455 n = a007455_list !! n
-- Reinhard Zumkeller, Jul 16 2012
(PARI) A007455(n)=[n%2*2+3, 1]*([3, 1; 2, 0]^(n\2-1))[, 1] \\ M. F. Hasler, Jun 19 2019

Crossrefs

Cf. A007481, A007482, A007484.

Sequence in context: A320353 A155989 A125557 * A034729 A115786 A252089

Adjacent sequences: A007452 A007453 A007454 * A007456 A007457 A007458

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Mira Bernstein

Status

approved