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

1, 2, 3, 7, 11, 25, 39, 89, 139, 317, 495, 1129, 1763, 4021, 6279, 14321, 22363, 51005, 79647, 181657, 283667, 646981, 1010295, 2304257, 3598219, 8206733, 12815247, 29228713, 45642179, 104099605, 162557031, 370756241, 578955451, 1320467933

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

A055099(n) = a(2*n+1) - a(2*n) = a(2*(n+1)) - a(2*n+1). - Reinhard Zumkeller, Oct 25 2015

Examples

			For n=2, there are the following three subsequences of [1,2] with the desired property: empty, [1], [1,2].
For n=3, there are the following seven subsequences of [1,2,3] with the desired property: empty, [1], [3], [1,2], [2,3], [1,3], [1,2,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 and W. O. J. Moser, Numbers of subsequences without isolated odd members, Fibonacci Quarterly 34:2 (1996), pp. 152-155.
• Index entries for linear recurrences with constant coefficients, signature (0, 3, 0, 2).

Crossrefs

Cf. A007455, A007482, A007484, A055099.

Programs

Haskell

a007481 n = a007481_list !! n
a007481_list = 1 : 2 : 3 : 7 : zipWith (+)
               (map (* 3) $ drop 2 a007481_list) (map (* 2) a007481_list)
-- Reinhard Zumkeller, Oct 25 2015

Mathematica

LinearRecurrence[{0,3,0,2},{1,2,3,7},40] (* Harvey P. Dale, Feb 29 2012 *)

PARI

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

Formula

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

G.f.: (x^3+2*x+1)/(-2*x^4-3*x^2+1). - Harvey P. Dale, Feb 29 2012

Extensions

More terms from James Sellers, Dec 24 1999