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

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

Author

N. J. A. Sloane, Mira Bernstein

Keywords

• nonn
• easy
• nice

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

Crossrefs

Cf. A007481, A007482, A007484.

Programs

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

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

PARI

A007455(n)=[n%2*2+3,1]*([3,1;2,0]^(n\2-1))[,1] \\ M. F. Hasler, Jun 19 2019

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