login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007483 a(n) = 3*a(n-1) + 2*a(n-2), with a(0)=1, a(1)=5.
(Formerly M3875)
16
1, 5, 17, 61, 217, 773, 2753, 9805, 34921, 124373, 442961, 1577629, 5618809, 20011685, 71272673, 253841389, 904069513, 3219891317, 11467812977, 40843221565, 145465290649, 518082315077, 1845177526529, 6571697209741 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Number of subsequences of [1,...,2n+1] in which each odd number has an even neighbor. The even neighbor must differ from the odd number by exactly 1.

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

a(n) is the upper left term in the (n+1)-th matrix power of [(1,4); (1,2)] and is the INVERT transform of (1, 4, 4*2, 4*2^2, 4*2^3, 4*2^4,...), i.e. of (1, 4, 8, 16, 32, 64, 128,...). The sequence is equal to row sums of an eigentriangle generated as follows: Let matrix A = an infinite lower triangle with (1, 4, 8, 16,...) in every column and B = a triangle with (1, 1, 5, 17, 61,...) as the rightmost diagonal and the rest zeros. Then the eigentriangle is A * B as follows: (1; 4, 1; 8, 4, 5; 16, 8, 20, 17;...) with sums (1, 5, 17, 61...). Individual rows can be recovered by taking the dot product of (1, 4, 8, 16,...) reversed and equal numbers of terms of(1, 1, 5, 17,...). For example, 61 = (16, 8, 4, 1) dot (1, 1, 5, 17) = (16 + 8 + 20 + 17). (End)

The sequence is equal to A007482 convolved with (1, 2, 0, 0, 0,...); i.e. (1 + 5x + 17x^2 + ...) = (1 + 3x + 11x^2 + 39x^3 + ...) * (1 + 2x). - Gary W. Adamson, Aug 08 2016

REFERENCES

C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci Numbers of Generalized Zykov Sums, Journal of Integer Sequences, Vol. 15, 2012, #12.7.8.

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

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..500

A. Burstein, S. Kitaev and T. Mansour, Independent sets in certain classes of (almost) regular graphs

Shalosh B. Ekhad, N. J. A. Sloane, and  Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249, 2015

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168, 2015

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

FORMULA

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

a(n)=(3/2 + sqrt(17)/2)^n*(1/2 + 7*sqrt(17)/34) + (1/2 - 7*sqrt(17)/34)*(3/2 - sqrt(17)/2)^n. - Paul Barry, Dec 08 2004

a(n-1) = Sum_{0<=k<=n} 2^(n-k)*A122542(n,k), n>=1. - Philippe Deléham, Oct 08 2006

a(n) = upper left term in the 2 X 2 matrix [1,2; 2,2]^(n+1). Also [a(n), a(n+1)] = the 2 X 2 matrix [0,1; 2,3]^(n+1) * [1,1]. Example: [0,1; 2,3]^4 * [1,1] = [61, 217]. - Gary W. Adamson, Mar 16 2008

Also, for n>=2, a(n)=[1,2;2,2]^(n-1)*[1,2]*[1,2]. - John M. Campbell, Jul 09 2011

a(n) = A007482(n) + 2*A007482(n-1). - R. J. Mathar, Sep 21 2012

This sequence seems to be generated by the floretion - 0.5'i + 0.5j' + 0.25'ii' + 0.25'jj' - 0.75'kk' + 'ij' - 'ji' - 0.5'jk' - 0.5'ki' - 0.75e ("emseq"). - Creighton Dement, Nov 25 2004

EXAMPLE

a(2) = 17 = (8, 4, 1) dot (1, 1, 5) = 8 + 4 + 5. - Gary W. Adamson, Aug 06 2016

MATHEMATICA

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

f[n_]:=2/(n+3); x=2; Table[x=f[x]; Numerator[x], {n, 0, 5!}]/2 (* Vladimir Joseph Stephan Orlovsky, Mar 12 2010 *)

LinearRecurrence[{3, 2}, {1, 5}, 24] (* Jean-François Alcover, Sep 26 2017 *)

PROG

(MAGMA) [Floor((3/2+Sqrt(17)/2)^n*(1/2+7*Sqrt(17)/34)+(1/2-7*Sqrt(17)/34)*(3/2-Sqrt(17)/2)^n)+1: n in [0..30]]; // Vincenzo Librandi, Jul 09 2011

(PARI) a(n)=([1, 2; 2, 2]^n*[1, 2]~*[1, 2])[1, 1] \\ Charles R Greathouse IV, Jul 10 2011

(Haskell)

a007483 n = a007483_list !! n

a007483_list = 1 : 5 : zipWith (+)

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

-- Reinhard Zumkeller, Nov 02 2015

CROSSREFS

Cf. A007482, A072272.

Sequence in context: A273422 A192146 A273607 * A273503 A273680 A273759

Adjacent sequences:  A007480 A007481 A007482 * A007484 A007485 A007486

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Sep 19 1994

EXTENSIONS

Definition simplified by N. J. A. Sloane, Aug 25 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 22 02:06 EDT 2017. Contains 293756 sequences.