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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001045 Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1.
(Formerly M2482 N0983)
516
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, 178956971, 357913941, 715827883, 1431655765, 2863311531, 5726623061 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Number of ways to tile a 3 X (n-1) rectangle with 1 X 1 and 2 X 2 square tiles.

Also, number of ways to tile a 2 X (n-1) rectangle with 1 X 2 dominoes and 2 X 2 squares. - Toby Gottfried, Nov 02 2008

Also a(n) counts each of the following four things: n-ary quasigroups of order 3 with automorphism group of order 3, n-ary quasigroups of order 3 with automorphism group of order 6, (n-1)-ary quasigroups of order 3 with automorphism group of order 2 and (n-2)-ary quasigroups of order 3. See the McKay-Wanless (2008) paper. - Ian Wanless (ian.wanless(AT)sci.monash.edu.au), Apr 28 2008

Also the number of ways to tie a necktie using n+2 turns. So three turns make an "oriental", four make a "four in hand" and for 5 turns there are 3 methods: "Kelvin", "Nicky" and "Pratt". The formula also arises from a special random walk on a triangular grid with side conditions (see Fink and Mao, 1999). - arne.ring(AT)epost.de, Mar 18 2001

Also the number of compositions of n+1 ending with an odd part (a(2)=3 because 3, 21, 111 are the only compositions of 3 ending with an odd part). Also the number of compositions of n+2 ending with an even part (a(2)=3 because 4, 22, 112 are the only compositions of 4 ending with an even part). - Emeric Deutsch, May 08 2001

Arises in study of sorting by merge insertions and in analysis of a method for computing GCDs - see Knuth reference.

Number of perfect matchings of a 2 X n grid upon replacing unit squares with tetrahedra (C_4 to K_4):

o----o----o----o...

| \/ | \/ | \/ |

| /\ | /\ | /\ |

o----o----o----o... - Roberto E. Martinez II, Jan 07 2002

Also the numerators of the reduced fractions in the alternating sum 1/2 - 1/4 + 1/8 - 1/16 + 1/32 - 1/64 + ... - Joshua Zucker, Feb 07 2002

Also, if A(n),B(n),C(n) are the angles of the n-orthic triangle of ABC then A(1) = Pi - 2A, A(n) = s(n)*Pi + (-2)^n*A where s(n) = (-1)^(n-1) * a(n) [1-orthic triangle = the orthic triangle of ABC, n-orthic triangle = the orthic triangle of the (n-1)-orthic triangle]. - Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr), Jun 05 2002

Also the number of words of length n+1 in the two letters s and t that reduce to the identity 1 by using the relations sss=1, tt=1 and stst=1. The generators s and t and the three stated relations generate the group S3. - John W. Layman, Jun 14 2002

Sums of pair of consecutive terms give all powers of 2 in increasing order. - Amarnath Murthy, Aug 15 2002

Excess clockwise moves (over anti-clockwise) needed to move a tower of size n to the clockwise peg is -(-1)^n(2^n - (-1)^n)/3; a(n)=its unsigned version. - Wouter Meeussen, Sep 01 2002

Also the absolute value of the number represented in base -2 by the string of n 1's, the negabinary repunit. The Mersenne numbers (A000225 and its subsequences) are the binary repunits. - Rick L. Shepherd, Sep 16 2002

Note that 3*a(n)+(-1)^n=2^n is significant for Pascal's triangle A007318. It arises from a Jacobsthal decomposition of Pascal's triangle illustrated by 1+7+21+35+35+21+7+1 = (7+35+1)+(1+35+7)+(21+21) = 43 + 43 + 42 = 3a(7)-1; 1+8+28+56+70+56+29+8+1 = (1+56+28)+(28+56+1)+(8+70+8) = 85 + 85 + 86 = 3a(8)+1. - Paul Barry, Feb 20 2003

Number of positive integers requiring exactly n signed bits in the nonadjacent form representation.

Equivalently, number of length-(n-1) strings with letters {0,1,2} where no two consecutive letters are nonzero, see example and fxtbook link. - Joerg Arndt, Nov 10 2012

Counts walks between adjacent vertices of a triangle. - Paul Barry, Nov 17 2003

Every amphichiral rational knot written in Conway notation is a palindromic sequence of numbers, not beginning or ending with 1. For example, for 4 <= n <= 12, the amphichiral rational knots are: 2 2, 2 1 1 2, 4 4, 3 1 1 3, 2 2 2 2, 4 1 1 4, 3 1 1 1 1 3, 2 3 3 2, 2 1 2 2 1 2, 2 1 1 1 1 1 1 2, 6 6, 5 1 1 5, 4 2 2 4, 3 3 3 3, 2 4 4 2, 3 2 1 1 2 3, 3 1 2 2 1 3, 2 2 2 2 2 2, 2 2 1 1 1 1 2 2, 2 1 2 1 1 2 1 2, 2 1 1 1 1 1 1 1 1 2. For the number of amphichiral rational knots for n=2k (k=1, 2, 3, ...), we obtain the sequence 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, ... - Slavik Jablan, Dec 26 2003

a(n+2) counts the binary sequences of total length n made up of codewords from C={0,10,11}. - Paul Barry, Jan 23 2004

Number of permutations with no fixed points avoiding 231 and 132.

The n-th entry (n>1) of the sequence is equal to the 2,2-entry of the n-th power of the unnormalized 4 X 4 Haar matrix: [1 1 1 0 / 1 1 -1 0 / 1 1 0 1 / 1 1 0 -1]. - Simone Severini, Oct 27 2004

a(n) = number of Motzkin (n+1)-sequences whose flatsteps all occur at level 1 and whose height is <=2. For example, a(4)=5 counts UDUFD, UFDUD, UFFFD, UFUDD, UUDFD. - David Callan, Dec 09 2004

a(n+1) gives row sums of A059260. - Paul Barry, Jan 26 2005

If (m + n) is odd, then 3*(a(m) + a(n)) is always of the form a^2 + 2*b^2, where a and b both equal powers of 2; consequently every factor of (a(m) + a(n)) is always of the form a^2 + 2*b^2. - Matthew Vandermast, Jul 12 2003

Number of "0,0" in f_{n+1}, where f_0 = "1" and f_{n+1} = a sequenece formed by changing all "1"s in f_n to "1,0" and all "0"s in f_n to "0,1" . - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Sep 22 2006

All prime Jacobsthal numbers A049883[n] = {3,5,11,43,683,2731,43691,...} have prime indices except a(4) = 5. All prime Jacobsthal numbers with prime indices (all but a(4) = 5) are of the form (2^p + 1)/3 - the Wagstaff primes A000979[n]. Indices of prime Jacobsthal numbers are listed in A107036[n] = {3,4,5,7,11,13,17,19,23,31,43,61,...}. For n>1 A107036[n] = A000978[n] Numbers n such that (2^n + 1)/3 is prime. - Alexander Adamchuk, Oct 03 2006

Correspondence: a(n)=b(n)*2^(n-1), where b(n) is the sequence of the arithmetic means of previous two terms defined by b(n)=1/2*(b(n-1)+b(n-2)) with initial values b(0)=0, b(1)=1; the g.f. for b(n) is B(x):=x/(1-(x^1+x^2)/2), so the g.f. A(x) for a(n) suffices A(x)=B(2*x)/2. Because b(n) converges to the limit lim (1-x)*B(x)=1/3*(b(0)+2*b(1))=2/3 (for x-->1), it follows that a(n)/2^(n-1) also converges to 2/3 (see also A103770). - Hieronymus Fischer, Feb 04 2006

Inverse: floor(log_2(a(n))=n-2 for n>=2. Also: log_2(a(n)+a(n-1))=n-1 for n>=1(see also A130249). Characterization: x is a Jacobsthal number if and only if there is a power of 4 (=c) such that x is a root of p(x)=9x(x-c)+(c-1)(2c+1) (see also the indicator sequence A105348). - Hieronymus Fischer, May 17 2007

This sequence counts the odd coefficients in the expansion of (1+x+x^2)^(2^n-1), n>=0. - Tewodros Amdeberhan (tewodros(AT)math.mit.edu), Oct 18 2007, Jan 08 2008

2^(n+1) = 2*A005578(n) + 2*a(n) + 2*A000975(n-1). Let A005578(n), a(n), A000975(n-1) = triangle (a, b, c). Then ((S-c), (S-b), (S-a)) = (A005578(n-1), a(n-1), A000975(n-2)). Example: (a, b, c) = (11, 11, 10) = (A005578(5), a(5), A000975(4). Then ((S-c), (S-b), (S-a)) = (6, 5, 5) = (A005578(4), a(4), A000975(3)). - Gary W. Adamson, Dec 24 2007

Sequence is identical to the absolute values of its inverse binomial transform. A similar result holds for [0,A001045*2^n]. - Paul Curtz, Jan 17 2008

From a(2) on (i.e., 1,3,5,11,21,...) also: least odd number such that the subsets of {a(2),...,a(n)} sum to 2^(n-1) different values, cf. A138000 and A064934. It is interesting to note the pattern of numbers occurring (or not occurring) as such a sum (A003158). - M. F. Hasler, Apr 09 2008

a(n) = term (5,1) of n-th power of the 5 X 5 matrix shown in A121231. - Gary W. Adamson, Oct 03 2008

A147612(a(n)) = 1. - Reinhard Zumkeller, Nov 08 2008

a(n+1) = Sum(A153778(i): 2^n <= i < 2^(n+1)). - Reinhard Zumkeller, Jan 01 2009

It appears that a(n) is also the number of integers between 2^n and 2^(n+1) that are divisible by 3 with no remainder. - John Fossaceca (john(AT)fossaceca.net), Jan 31 2009

Number of pairs of consecutive odious (or evil) numbers between 2^(n+1) and 2^(n+2), inclusive. - T. D. Noe, Feb 05 2009

Equals eigensequence of triangle A156319. - Gary W. Adamson, Feb 07 2009

A three-dimensional interpretation of a(n+1) is that it gives the number of ways of filling a 2 X 2 X n hole with 1 X 2 X 2 bricks. - Martin Griffiths (griffm(AT)essex.ac.uk), Mar 28 2009

Starting with offset 1 = INVERTi transform of A002605: (1, 2, 6, 16, 44,...). - Gary W. Adamson, May 12 2009

Convolved with (1, 2, 2, 2,...) = A000225: (1, 3, 7, 15, 31,...). - Gary W. Adamson, May 23 2009

The product of a pair of successive terms is always a triangular number. - Giuseppe Ottonello, Jun 14 2009

Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-2, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=(-1)^(n-1)det(A). - Milan Janjic, Jan 26 2010

Let R denote the irreducible representation of the symmetric group S_3 of dimension 2, and let s and t denote respectively the sign and trivial irreducible representations of dimension 1. The decomposition of R^n into irreducible representations consists of a(n) copies of R and a(n-1) copies of each of s and t. - Andrew Rupinski, Mar 12 2010

As a fraction: 1/88 = 0.0113636363.. or 1/9898 = 0.00010103051121.. - M. Dols (markdols99(AT)yahoo.com), May 18 2010

Starting with "1" = the INVERT transform of (1, 0, 2, 0, 4, 0, 8,...); e.g., a(7) = 43 = (1, 1, 1, 3, 5, 11, 21) dot (8, 0, 4, 0, 2, 0, 1) = (8 + 4 + 10 + 21) = 43. - Gary W. Adamson, Oct 28 2010

Rule 28 elementary cellular automaton generates this sequence. - Paul Muljadi, Jan 27 2011

This is a divisibility sequence. - Michael Somos, Feb 06 2011

(Start) Let U be the unit-primitive matrix (see [Jeffery])

U=U_(6,2)=

(0 0 1)

(0 2 0)

(2 0 1).

Then a(n+1)=(Trace(U^n))/3, a(n+1)=((U^n)_{3,3})/3, a(n)=((U^n)_{1,3})/3 and a(n)=((U^(n+1))_{1,1})/2. - L. Edson Jeffery, Apr 04 2011

The sequence emerges in using iterated deletion of strictly dominated strategies to establish the best-response solution to the Cournot duopoly problem as a strictly dominant strategy. The best response of firm 1 to firm 2's chosen quantity is given by q*_1 = 1/2(a-c-q_2), where a is reservation price, c is marginal cost, and q_2 is firm two's chosen quantity. given that q_2 is in [o, a-c], q*_1 must be in [o, 1/2(a-c)]. Since costs are symmetric, we know q_2 is in [0, 1/2(a-c)]. Then we know q*_1 is in [1/4(a-c), 1/2(a-c)]. Continuing in this way, the sequence of bounds we get (factoring out a-c) is {1/2, 1/4, 3/8, 5/16, ...}; the numerators are the Jacobsthal numbers. - Michael Chirico, Sep 10 2011

The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n.  For n>=2, 3*a(n-1) equals the number of 3-colored compositions of n with all parts >=2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011

This sequence is connected with the Collatz problem. We consider the array T(i,j) where the i-th row gives the parity trajectory of i, for example for i = 6, the infinite trajectory is 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1... and T(6,j) = [0,1,0,1,0,0,0,0,1,0,0,1,...,1,0,0,1,...]. Now, we consider the sum of the digits "1" of each column. We obtain the sequence a(n) = Sum_{k=1..2^n} T(k,n) = Sum _{k=1..2^n} digits "1" of the n-th column. Because a(n) + a(n+1) = 2^n, then a(n+1) = Number of digits "0" among the 2^n elements of the n-th column. - Michel Lagneau, Jan 11 2012

3!*a(n-1) is apparently the trace of the n-th power of the adjacency matrix of the complete 3-graph, a 3 X 3 matrix with diagonal elements all zero and off-diagonal all ones. The off-diagonal elements for the n-th power are all equal to a(n) while each diagonal element seems to be a(n)+1 for an even power and a(n)-1 for an odd. These are related to the lengths of closed paths on the graph (see Delfino and Viti's paper). - Tom Copeland, Nov 06 2012

2^n * a(-n) = (-1)^(n-1) * a(n), which extends the sequence to negative indices: ..., -5/16, 3/8, -1/4, 1/2, 0, 1, 1, 3, 5,... The eigensequence property with respect to the binomial transform mentioned in my comment of Jan 17 2008 is still valid if the term a(-1) is added to the array of the sequence and its iterated higher-order differences in subsequent rows:

0,   1/2, 1/2, 3/2, 5/2, 11/2, ...

1/2,   0,   1,   1,   3,    5, ...

-1/2,  1,   0,   2,   2,    6, ...

3/2,  -1,   2,   0,   4,    4, ...

-5/2,  3,  -2,   4,   0,    8, ...

11/2, -5,   6,  -4,   8,    0. ...

The main diagonal in this array contains zeros. - Paul Curtz, Dec 11 2012

Assign to a triangle T(n,0) = 1 and T(n+1,1) = n; T(r,c) = T(r-1,c-1) + T(r-1,c-2) + T(r-2,c-2).  Then T(n+1,n) - T(n,n) = a(n). - J. M. Bergot, May 02 2013

a(n+1) counts clockwise walks on n points on a circle which take steps of length 1 and 2, return to the starting point after two full circuits, and do not duplicate any steps (USAMO 2013, problem 5). - Kiran S. Kedlaya, May 11 2013

Define an infinite square array m by m(n,0) = m(0,n) = a(n) in top row and left column and m(i,j)=m(i,j-1)+m(i-1,j-1) otherwise, then m(n+1,n+1)=3^(n-1). - J. M. Bergot, May 10 2013

a(n) is the number of compositions (ordered partitions) of n-1 into one sort of 1's and two sorts of 2's.  Example: the a(4)=5 compositions of 3 are 1+1+1, 1+2, 1+2', 2+1 and 2'+1. - Bob Selcoe, Jun 24 2013

Without 0, a(n)/2^n equals the probability that n will occur as a partial sum in a randomly-generated infinite sequence of 1s and 2s.  The limiting ratio is 2/3. - Bob Selcoe, Jul 04 2013

Number of conjugacy classes of Z/2Z x Z/2Z in GL(2,2^(n+1)). - Jared Warner, Aug 18 2013

a(n+1) is the top left entry in the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 0]. - R. J. Mathar, Feb 03 2014

a(n-1) is the top left entry of the n-th power of any of the six 3 X 3 matrices [0, 1, 0; 1, 1, 1; 0, 1, 0], [0, 1, 1; 0, 1, 1; 1, 1, 0], [0, 0, 1; 1, 1, 1; 1, 1, 0], [0, 1, 1; 1, 0, 1; 0, 1, 1], [0, 0, 1; 0, 0, 1; 1, 1, 1] or [0, 1, 0; 1, 0, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014

This is the only integer sequence from the family of homogeneous linear recurrence of order 2 given by a(n) = k*a(n-1)+t*a(n-2) with positive integer coefficients k and t and initial values a(0)=0 and a(1)=1 whose ratio a(n+1)/a(n) converges to 2 as n approaches infinity. - Felix P. Muga II, Mar 14 2014

It is the Lucas sequence U(1,-2). - Felix P. Muga II, Mar 21 2014

REFERENCES

Mohammad K. Azarian, Limit of Nested Square Roots, Problem B-664, Fibonacci Quarterly, Vol. 28, No. 2, May 1990, p. 182.  Solution published in Vol. 29, No. 2, May 1991, p. 182.

L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., Representations for a special sequence, Fib. Quart., 10 (1972), 499-518, 550.

Charles K. Cook and Michael R. Bacon, Some identities for Jacobsthal and Jacobsthal-Lucas numbers satisfying higher order recurrence relations, Annales Mathematicae et Informaticae, 41 (2013) pp. 27-39; http://ami.ektf.hu/uploads/papers/finalpdf/AMI_41_from27to39.pdf.

D. E. Daykin, D. J. Kleitman and D. B. West, The number of meets between two subsets of a lattice, J. Combin. Theory, A 26 (1979), 135-156.

Th. Fink and Y. Mao. The 85 ways to tie a tie, Fourth Estate, London, 1999; Die 85 Methoden eine Krawatte zu binden. Hoffmann und Kampe, Hamburg, 1999.

International Mathematical Olympiad 2001, Hong Kong Preliminary Selection Contest Problem #16.

Jablan S. and Sazdanovic R., LinKnot: Knot Theory by Computer, World Scientific Press, 2007. See p. 80.

D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1, Eq. 13.

T. Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.

S. L. Levine, Suppose more rabbits are born, Fib. Quart., 26 (1988), 306-311.

B. D. McKay and I. M. Wanless, A census of small latin hypercubes, SIAM J. Discrete Math. 22, (2008) 719-736.

G. Myerson and A. J. van der Poorten, Some problems concerning recurrence sequences, Amer. Math. Monthly, 102 (1995), 698-705.

Sam Northshield, "Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,...", Amer. Math. Month., Vol. 117 (7), pp. 581-598, 2010.

D. Panario, M. Sahin, Q. Wang, A family of Fibonacci-like conditional sequences, INTEGERS, Vol. 13, 2013, #A78.

M. Rahmani, The Akiyama-Tanigawa matrix and related combinatorial identities, Linear Algebra and its Applications 438 (2013) 219-230. - From N. J. A. Sloane, Dec 26 2012

S. Roman, Introduction to Coding and Information Theory, Springer Verlag, 1996, 41-42.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

Two-Year College Math. Jnl., 28 (1997), p. 76.

USA Mathematical Olympiad 2013, problem 5 (proposed by Sam Vandervelde).

Robert M. Young, "Excursions in Calculus", MAA, 1992, p. 239

G. B. M. Zerr, Problem 64, American Mathematical Monthly, vol. 3, no. 12, 1896 (p. 311).

LINKS

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

Joerg Arndt, Fxtbook, pp.315-318

P. Barry, On sequences with {-1, 0, 1} Hankel transforms, Arxiv preprint arXiv:1205.2565, 2012. - From N. J. A. Sloane, Oct 18 2012

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

W. Bosma, Signed bits and fast exponentiation

G. Bowlin and M. G. Brin, Coloring Planar Graphs via Colored Paths in the Associahedra, arXiv preprint arXiv:1301.3984, 2013. - From N. J. A. Sloane, Feb 12 2013

Gesualdo Delfino and Jacopo Viti, Potts q-color field theory and scaling random cluster model, arXiv:1104.4323, 2011.

Peter E. Finch, From spin to anyon notation: The XXZ Heisenberg model as a D_3 (or su(2)_4) anyon chain, Arxiv preprint arXiv:1201.4470, 2012

D. D. Frey and J. A. Sellers, Jacobsthal Numbers and Alternating Sign Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.3

Richard K. Guy, Tanya Khovanova, and Julian Salazar, Conway's subprime Fibonacci sequences, arXiv:1207.5099 [math.NT]

Lee Hae-hwang, Illustration of initial terms in terms of rosemary plants

S. Heubach, Tiling an m-by-n area with squares of size up to k-by-k (m<=5), Congressus Numerantium 140 (1999), 43-64.

A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 56. Book's website

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 142

L. E. Jeffery, Unit-primitive matrices

T. Mansour and A. Robertson, Refined restricted permutations....

G. Myerson and A. J. van der Poorten, Some problems concerning recurrence sequences, Amer. Math. Monthly, 102 (1995), 698-705.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

E. Schlemm, On the expected number of successes in a sequence of nested Bernoulli trials, arXiv preprint arXiv:1303.4979, 2013

Eric Weisstein's World of Mathematics, Jacobsthal Number, Negabinary, Repunit, Rule 28.

Wikipedia, Elementary cellular automaton

Index entries for sequences related to Chebyshev polynomials.

Index to sequences with linear recurrences with constant coefficients, signature (1,2).

FORMULA

a(n) = 2^(n-1) - a(n-1). a(n) = 2*a(n-1) - (-1)^n = (2^n - (-1)^n)/3.

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

E.g.f.: (exp(2*x)-exp(-x))/3.

a(2*n) = 2*a(2*n-1)-1 for n>=1, a(2*n+1) = 2*a(2*n)+1 for n>=0. - Lee Hae-hwang (mathmaniac(AT)empal.com), Oct 11 2002; corrected by Mario Catalani (mario.catalani(AT)unito.it), Dec 04 2002

Also a(n) is the coefficient of x^(n-1) in the bivariate Fibonacci polynomials F(n)(x, y)=x*F(n-1)(x, y)+y*F(n-2)(x, y), with y=2*x^2. - Mario Catalani (mario.catalani(AT)unito.it), Dec 04 2002

a(n) = sum(k=1..n, binomial(n, k)*(-1)^(n+k)*3^(k-1) ). - Paul Barry, Apr 02 2003

The ratios a(n)/2^(n-1) converge to 2/3 and every fraction after 1/2 is the arithmetic mean of the two preceding fractions. - Gary W. Adamson, Jul 05 2003

a(n) = U(n-1, i/(2*sqrt(2)))*(-i*sqrt(2))^(n-1) with i^2=-1. - Paul Barry, Nov 17 2003

a(n+1) = sum(k=0..ceil(n/2), 2^k*binomial(n-k, k)). - Benoit Cloitre, Mar 06 2004

a(2*n) = A002450(n) = (4^n - 1)/3; a(2*n+1) = A007583(n) = (2^(2*n+1) + 1)/3. - Philippe Deléham, Mar 27 2004

a(n) = round(2^n/3) = (2^n + (-1)^(n-1))/3 so lim n->inf 2^n/a(n) = 3. - Gerald McGarvey, Jul 21 2004

a(n) = sum(k=0..n-1, (-1)^k*2^(n-k-1) ) = sum(k=0..n-1, 2^k(-1)^(n-k-1) ). - Paul Barry, Jul 30 2004

a(n+1) = sum(k=0..n, binomial(k, n-k)*2^(n-k) ). - Paul Barry, Oct 07 2004

a(n) = sum(k=0..n-1, W(n-k, k)*(-1)^(n-k)*binomial(2*k,k) ), W(n, k) as in A004070. - Paul Barry, Dec 17 2004

a(n) = sum(k=0..n, k*binomial(n-1, (n-k)/2)*(1+(-1)^(n+k))*floor((2*k+1)/3) ); a(n+1)=sum(k=0..n, k*binomial(n-1, (n-k)/2)*(1+(-1)^(n+k))*(A042965(k)+0^k) ). - Paul Barry, Jan 17 2005

a(n+1) = ceiling(2^n/3)+floor(2^n/3)=(ceiling(2^n/3))^2-(floor(2^n/3))^2; a(n+1) = A005578(n)+A000975(n-1)=A005578(n)^2-A000975(n-1)^2. - Paul Barry, Jan 17 2005

a(n+1) = sum(k=0..n, sum(j=0..n, (-1)^(n-j)*binomial(j, k) ) ). - Paul Barry, Jan 26 2005

Let M = [1, 1, 0;1, 0, 1;0, 1, 1], then a(n) = (M^n)[2, 1], also matrix characteristic polynomial x^3 - 2*x^2 - x + 2 defines the three step recursion a(0)=0, a(1)=1, a(2)=1, a(n)=2a(n-1)+a(n-2)-2a(n-3) for n>2. - Lambert Klasen (lambert.klasen(AT)gmx.net), Jan 28 2005

a(n) = ceiling(2^(n+1)/3)-ceiling(2^n/3)=A005578(n+1)-A005578(n). - Paul Barry, Oct 08 2005

a(n) = floor(2^(n+1)/3)-floor(2^n/3)=A000975(n)-A000975(n-1). - Paul Barry, Oct 08 2005

a(n) = sum(k=0..floor(n, 3), binomial(n, f(n-1)+3*k) ); a(n) = sum(k=0..floor(n/3), binomial(n, f(n-2)+3*k) ), where f(n)=A080424(n). - Paul Barry, Feb 20 2003

a(2*n) = Product(d divides n, cyclotomic(d,4))/3; a(2*n+1) = Product(d divides 2*n+1, cyclotomic(2*d,2))/3. - Miklos Kristof, Mar 07 2007

From Hieronymus Fischer, Apr 23 2007: (Start)

The a(n) are closely related to nested square roots; this is 2*sin(2^(-n)*Pi/2*a(n))=sqr(2-sqr(2-sqr(2-sqr(...sqr(2)))...){n-times the '2', n>=0}.

Also 2*cos(2^(-n)*Pi*a(n))=sqr(2-sqr(2-sqr(2-sqr(...sqr(2)))...){(n-1)-times the '2', n>=1} as well as

2*sin(2^(-n)*3/2*Pi*a(n))=sqr(2+sqr(2+sqr(2+sqr(...sqr(2)))...){n-times the '2', n>=0} and

2*cos(2^(-n)*3*Pi*a(n))=-sqr(2+sqr(2+sqr(2+sqr(...sqr(2)))...){(n-1)-times the '2', n>=1}.

a(n) = 2^(n+1)/Pi*arcsin(b(n+1)/2) where b(n) is defined recursively by b(0)=2, b(n)=sqr(2-b(n-1)).

There is a similar formula regarding the arccos function, this is a(n) = 2^n/Pi*arccos(b(n)/2).

With respect to the sequence c(n) defined recursively by c(0)=-2, c(n)=sqr(2+c(n-1)) the following formulas hold true: a(n) = 2^n/3*(1-(-1)^n*(1-2/Pi*arcsin(c(n+1)/2)); a(n) = 2^n/3*(1-(-1)^n*(1-1/pi*arccos(-c(n)/2)).

(End)

sum(k=0..n, A039599(n,k)*a(k)) = A049027(n), for n>=1 . - Philippe Deléham, Jun 10 2007

sum(k=0..n, A039599(n,k)*a(k+1) = A067336(n). - Philippe Deléham, Jun 10 2007

Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0,] = [A005578(n), a(n), A000975(n-1]. - Gary W. Adamson, Dec 24 2007

a(n) + a(n+5) = 11*2^n. - Paul Curtz, Jan 17 2008

a(n) = sum(k=1..n, K(2, k)*a(n - k) ), where K(n,k) = k if 0<=k<= n and K(n,k)=0 else. (When using such a K-coefficient several different arguments to K or several different definitions of K may lead to the same integer sequence. For example, the Fibonacci sequence can be generated in several ways using the K-coefficient.) - Thomas Wieder, Jan 13 2008

a(n) + a(n+2*k+1) = a(2*k+1)*2^n. - Paul Curtz, Feb 12 2008

a(n) = lower left term in the 2 X 2 matrix [0,2; 1,1]^n - Gary W. Adamson, Mar 02 2008

a(n+1) = sum(k=0..n, A109466(n,k)*(-2)^(n-k)). -Philippe Deléham, Oct 26 2008

a(n) = sqrt( 8*a(n-1)*a(n-2) + 1 ). E.g., sqrt(3*5*8+1)=11, sqrt(5*11*8+1) = 21. - Giuseppe Ottonello, Jun 14 2009

If p[i] = fibonacci(i-1) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=det(A). - Milan Janjic, May 08 2010

a(p-1) = p*A007663(n)/3 if n>1, and a(p-1) = p*A096060(n) if n>2, with p=prime(n). - Jonathan Sondow, Jul 19 2010

Algebraically equivalent to replacing the 5's with 9's in the explicit (Binet) formula for the n-th term in the Fibonacci sequence: The formula for the n-th term in the Fibonacci sequence is F(n)=((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^n*sqrt(5)). Replacing the 5's with 9's gives ((1+sqrt(9))^n-(1-sqrt(9))^n)/(2^n*sqrt(9)) = (2^n+(-1)^(n+1))/3 = (2^n-(-1)^(n))/3 = a(n). - Jeffrey R. Goodwin, May 27 2011

For n>1, a(n) = A000975(n-1) + (1+(-1)^(n-1))/2. - Vladimir Shevelev, Feb 27 2012

From Sergei N. Gladkovskii, Jun 12 2012: (Start)

G.f.: x/(1-x-2*x^2)=G(0)/3; G(k)= 1 -((-1)^k)/(2^k - 2*x*4^k/(2*x*2^k - ((-1)^k)/G(k+1))); (continued fraction 3 kind, 3-step).

E.g.f.: G(0)/3; G(k) = 1 -((-1)^k)/(2^k - 2*x*4^k/(2*x*2^k - ((-1)^k)*(k+1)/G(k+1))); (continued fraction 3rd kind, 3-step). (End)

a(n) = 2^k * a(n-k) + (-1)^(n+k)*a(k). - Paul Curtz, Jean-François Alcover, Dec 11 2012

a(n) = sqrt((A014551(n))^2 + (-1)^(n-1)*2^(n+2))/3. - Vladimir Shevelev, Mar 13 2013

G.f.: Q(0)/3, where Q(k)= 1 - 1/(4^k - 2*x*16^k/(2*x*4^k - 1/(1 + 1/(2*4^k - 8*x*16^k/(4*x*4^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 21 2013

G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(2*k+1 + 2*x)/( x*(2*k+2 + 2*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 29 2013

G.f.: Q(0) -1, where Q(k) = 1 + 2*x^2 + (k+2)*x - x*(k+1 + 2*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 06 2013

a(n+2) = sum_{k=0..n} A108561(n,k)*(-2)^k. - Philippe Deléham, Nov 17 2013

a(n) = (sum_{1<=k<=n, k odd} C(n,k)*3^(k-1))/2^(n-1). - Vladimir Shevelev, Feb 05 2014

a(-n) = -(-1)^n * a(n) / 2^n for all n in Z. - Michael Somos, Mar 18 2014

a(n)=(-1)^(n-1)*sum(k=0,..,n-1, A135278(n-1,k)*(-3)^k) = [2^n-(-1)^n]/3 = (-1)^(n-1)*sum(k=0,..,n-1, (-2)^k). Equals (-1)^(n-1)*Phi(n,-2), where Phi is the cyclotomic polynomial when n is an odd prime. (For n>0.) - Tom Copeland, Apr 14 2014

EXAMPLE

a(2) = 3 because the tiling of the 3 X 2 rectangle has either only 1 X 1 tiles, or one 2 X 2 tile in one of two positions (together with two 1 X 1 tiles).

From Joerg Arndt, Nov 10 2012: (Start)

The a(6)=21 length-5 ternary words with no two consecutive letters nonzero are (dots for zeros)

[ 1]   [ . . . . ]

[ 2]   [ . . . 1 ]

[ 3]   [ . . . 2 ]

[ 4]   [ . . 1 . ]

[ 5]   [ . . 2 . ]

[ 6]   [ . 1 . . ]

[ 7]   [ . 1 . 1 ]

[ 8]   [ . 1 . 2 ]

[ 9]   [ . 2 . . ]

[10]   [ . 2 . 1 ]

[11]   [ . 2 . 2 ]

[12]   [ 1 . . . ]

[13]   [ 1 . . 1 ]

[14]   [ 1 . . 2 ]

[15]   [ 1 . 1 . ]

[16]   [ 1 . 2 . ]

[17]   [ 2 . . . ]

[18]   [ 2 . . 1 ]

[19]   [ 2 . . 2 ]

[20]   [ 2 . 1 . ]

[21]   [ 2 . 2 . ]

(End)

G.f. = x + x^2 + 3*x^3 + 5*x^4 + 11*x^5 + 21*x^6 + 43*x^7 + 85*x^8 + 171*x^9 + ...

MAPLE

A001045:=-1/(z+1)/(2*z-1); # Simon Plouffe in his 1992 dissertation.

with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S, card > 0), S=Sequence(U, card > 0), U=Sequence(Z, card >1)}, unlabeled]: seq(count(SeqSeqSeqL, size=j), j=1..34); # Zerinvary Lajos, Apr 04 2009

A001045 := proc(n)

  (2^n-(-1)^n)/3 ;

end proc: # R. J. Mathar, Dec 18 2012

MATHEMATICA

a[n_] := (2^n - (-1)^n)/3; Table[ a[n], {n, 0, 33}] (* Robert G. Wilson v, Dec 05 2005 *)

Array[(2^# - (-1)^#)/3 &, 33, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)

LinearRecurrence[{1, 2}, {0, 1}, 40] (* Harvey P. Dale, Nov 30 2011 *)

PROG

(PARI) {a(n) = (2^n - (-1)^n) / 3};

(PARI) a(n)=if(n==0, 0, if(n==1, 1, if(n==2, 1, 2*a(n-1)+a(n-2)-2*a(n-3)))) for(i=0, 15, print1(a(i), ", ")) M=[1, 1, 0; 1, 0, 1; 0, 1, 1]; for(i=0, 15, print1((M^i)[2, 1], ", ")) /* Klasen */

(Sage) [lucas_number1(n, 1, -2) for n in xrange(0, 34)] # Zerinvary Lajos, Apr 22 2009

(Haskell)

a001045 = (`div` 3) . (+ 1) . a000079

a001045_list = 0 : 1 :

   zipWith (+) (map (2 *) a001045_list) (tail a001045_list)

-- Reinhard Zumkeller, Mar 24 2013, Jan 05 2012, Feb 05 2011

(Maxima)

a[0]:0$

a[n]:=2^(n-1)-a[n-1]$

A001045(n):=a[n]$

makelist(A001045(n), n, 0, 30); /* Martin Ettl, Nov 05 2012 */

(Python) dict = {0:0, 1:1}... def generateA001045(n): '''generate A001045 as a sequence with n terms''' ... if n not in dict: ... i = max(dict.keys()) ... while i < n: ... i += 1 ... dict[i] = dict[i-1] + 2*dict[i-2] ... return dict.values()[:n]

CROSSREFS

Partial sums of this sequence give A000975, where there are additional comments from B. E. Williams and Bill Blewett on the tie problem. Cf. A049883, A026644.

A002487(a(n)) = A000045(n).

Row sums of A059260, A156667 and A134317. Equals A026644(n-2)+1 for n > 1.

a(n)= A073370(n-1, 0), n>=1 (first column of triangle).

See also A081857.

Cf. A000978, A000979.

Cf. A049883 = primes in this sequence, A107036 = indices of primes,A129738.

Cf. A019322 A066845, A105348, A130249, A130250, A130253, A134317, A005578, A002083, A002487, A113405, A138000, A064934, A003158, A175286 (Pisano periods).

Cf. A147613.

Cf. A156319, A002605, A000225.

Cf. A052129

Sequence in context: A154917 A167167 * A077925 A084230 A077465 A146574

Adjacent sequences:  A001042 A001043 A001044 * A001046 A001047 A001048

KEYWORD

nonn,nice,easy,core,tabl,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from James A. Sellers, Dec 23 1999

Zerr reference from Len Smiley (smiley(AT)math.uaa.alaska.edu), May 21 2001

More terms from Simone Severini, Oct 27 2004

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 18 11:35 EDT 2014. Contains 240707 sequences.