OFFSET

0,2

COMMENTS

The even neighbor must differ from the odd number by exactly one.

If we defined this sequence by the recurrence (a(n) = 3*a(n-1) + 2*a(n-2)) that it satisfies, we could prefix it with an initial 0.

a(n) equals term (1,2) in M^n, M = the 3 X 3 matrix [1,1,2; 1,0,1; 2,1,1]. - Gary W. Adamson, Mar 12 2009

a(n) equals term (2,2) in M^n, M = the 3 X 3 matrix [0,1,0; 1,3,1; 0,1,0]. - Paul Barry, Sep 18 2009

From Gary W. Adamson, Aug 06 2010: (Start)

Starting with "1" = INVERT transform of A002605: (1, 2, 6, 16, 44, ...).

Example: a(3) = 39 = (16, 6, 2, 1) dot (1, 1, 3, 11) = (16 + 6 + 6 + 11). (End)

Pisano periods: 1, 1, 4, 1, 24, 4, 48, 2, 12, 24, 30, 4, 12, 48, 24, 4,272, 12, 18, 24, ... . - R. J. Mathar, Aug 10 2012

A007482 is also the number of ways of tiling a 3 X n rectangle with 1 X 1 squares, 2 X 2 squares and 2 X 1 (vertical) dominoes. - R. K. Guy, May 20 2015

With offset 1 (a(0) = 0, a(1) = 1) this is a divisibility sequence. - Michael Somos, Jun 03 2015

Number of elements of size 2^(-n) in a fractal generated by the second-order reversible cellular automaton, rule 150R (see the reference and the link). - Yuriy Sibirmovsky, Oct 04 2016

a(n) is the number of compositions (ordered partitions) of n into parts 1 (of three kinds) and 2 (of two kinds). - Joerg Arndt, Oct 05 2016

a(n) equals the number of words of length n over {0,1,2,3,4} in which 0 and 1 avoid runs of odd lengths. - Milan Janjic, Jan 08 2017

Start with a single cell at coordinates (0, 0), then iteratively subdivide the grid into 2 X 2 cells and remove the cells that have two '1's in their modulo 3 coordinates. a(n) is the number of cells after n iterations. Cell configuration converges to a fractal with approximate dimension 1.833. - Peter Karpov, Apr 20 2017

This is the Lucas sequence U(P=3,Q=-2), and hence for n>=0, a(n+2)/a(n+1) equals the continued fraction 3 + 2/(3 + 2/(3 + 2/(3 + ... + 2/3))) with n 2's. - Greg Dresden, Oct 06 2019

REFERENCES

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

Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002, p. 439.

LINKS

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

Alexander Burstein and Opel Jones, Enumeration of Dumont permutations avoiding certain four-letter patterns, arXiv:2002.12189 [math.CO], 2020.

R. K. Guy and William O. J. Moser, Numbers of subsequences without isolated odd members, Fibonacci Quarterly, 34, No. 2, 152-155 (1996). Math. Rev. 97d:11017.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 442

Peter Karpov, InvMem, Item 26

Peter Karpov, Illustration of initial terms (n = 1..8)

Yuriy Sibirmovsky, A fractal with number of elements described by a(n)

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

FORMULA

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

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

a(n) = (ap^(n+1)-am^(n+1))/(ap-am), where ap = (3+sqrt(17))/2 and am = (3-sqrt(17))/2.

Let b(0) = 1, b(k) = floor(b(k-1)) + 2/b(k-1); then, for n>0, b(n) = a(n)/a(n-1). - Benoit Cloitre, Sep 09 2002

The Hankel transform of this sequence is [1,2,0,0,0,0,0,0,0,...]. - Philippe Deléham, Nov 21 2007

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)2^k*3^(n-2k). - Paul Barry, Apr 23 2005

a(n) = Sum_{k=0..n} A112906(n,k). - Philippe Deléham, Nov 21 2007

a(n) = - a(-2-n) * (-2)^(n+1) for all n in Z. - Michael Somos, Jun 03 2015

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

a(n) = 3^n*hypergeom([(1-n)/2,-n/2], [-n], -8/9) for n>=1. - Peter Luschny, Jun 28 2017

a(n) = round(((sqrt(17) + 3)/2)^(n+1)/sqrt(17)). The distance of the argument from the nearest integer is about 1/2^(n+3). - M. F. Hasler, Jun 16 2019

E.g.f.: (1/17)*exp(3*x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2)). - Stefano Spezia, Oct 07 2019

a(n) = (sqrt(2)*i)^n * ChebyshevU(n, -3*i/(2*sqrt(2))). - G. C. Greubel, Dec 24 2021

G.f.: 1/(1 - 3*x - 2*x^2) = Sum_{n >= 0} x^n * Product_{k = 1..n} (k + 2*x + 2)/(1 + k*x) (a telescoping series). Cf. A015518. - Peter Bala, May 08 2024

EXAMPLE

G.f. = 1 + 3*x + 11*x^2 + 39*x^3 + 139*x^4 + 495*x^5 + 1763*x^6 + ...

From M. F. Hasler, Jun 16 2019: (Start)

For n = 0, (1, ..., 2n) = () is the empty sequence, which is equal to its only subsequence, which satisfies the condition voidly, whence a(0) = 1.

For n = 1, (1, ..., 2n) = (1, 2); among the four subsequences {(), (1), (2), (1,2)} only (1) does not satisfy the condition, whence a(1) = 3.

For n = 2, (1, ..., 2n) = (1, 2, 3, 4); among the sixteen subsequences {(), ..., (1,2,3,4)}, the 5 subsequences (1), (3), (1,3), (2,3,4) and (1,2,3,4) do not satisfy the condition, whence a(2) = 16 - 5 = 11.

(End)

MAPLE

a := n -> `if`(n=0, 1, 3^n*hypergeom([(1-n)/2, -n/2], [-n], -8/9)):

seq(simplify(a(n)), n = 0..23); # Peter Luschny, Jun 28 2017

MATHEMATICA

a[n_]:=(MatrixPower[{{1, 4}, {1, 2}}, n].{{1}, {1}})[[2, 1]]; Table[a[n], {n, 0, 40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)

LinearRecurrence[{3, 2}, {1, 3}, 30] (* Harvey P. Dale, May 25 2013 *)

a[ n_] := Module[ {m = n + 1, s = 1}, If[ m < 0, {m, s} = -{m, (-2)^m}]; s SeriesCoefficient[ x / (1 - 3 x - 2 x^2), {x, 0, m}]]; (* Michael Somos, Jun 03 2015 *)

a[ n_] := With[{m = n + 1}, If[ m < 0, (-2)^m a[ -m], Expand[((3 + Sqrt[17])/2)^m - ((3 - Sqrt[17])/2)^m ] / Sqrt[17]]]; (* Michael Somos, Oct 13 2016 *)

PROG

(Sage) [lucas_number1(n, 3, -2) for n in range(1, 25)] # Zerinvary Lajos, Apr 22 2009

(PARI) {a(n) = 2*imag(( (3 + quadgen(68)) / 2)^(n+1))}; /* Michael Somos, Jun 03 2015 */

(Haskell)

a007482 n = a007482_list !! (n-1)

a007482_list = 1 : 3 : zipWith (+)

(map (* 3) $ tail a007482_list) (map (* 2) a007482_list)

-- Reinhard Zumkeller, Oct 21 2015

(Maxima) a(n) := if n=0 then 1 elseif n=1 then 3 else 3*a(n-1)+2*a(n-2);

makelist(a(n), n, 0, 12); /* Emanuele Munarini, Jun 28 2017 */

(Magma) I:=[1, 3]; [n le 2 select I[n] else 3*Self(n-1) + 2*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 16 2018

CROSSREFS

KEYWORD

nonn,easy,nice

AUTHOR

STATUS

approved