

A001045


Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n1) + 2*a(n2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer to 2^n/3.
(Formerly M2482 N0983)


668



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;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Don Knuth points out (personal communication) that Jacobsthal may never have seen the actual values of this sequence. However, Horadam uses the name "Jacobsthal sequence", such an important sequence needs a name, and there is a law that says the name for something should never be that of its discoverer.  N. J. A. Sloane, Dec 26 2020
Number of ways to tile a 3 X (n1) rectangle with 1 X 1 and 2 X 2 square tiles.
Also, number of ways to tile a 2 X (n1) 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: nary quasigroups of order 3 with automorphism group of order 3, nary quasigroups of order 3 with automorphism group of order 6, (n1)ary quasigroups of order 3 with automorphism group of order 2 and (n2)ary quasigroups of order 3. See the McKayWanless (2008) paper.  Ian Wanless, 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):
oooo...
 \/  \/  \/ 
 /\  /\  /\ 
oooo...  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 northic triangle of ABC then A(1) = Pi  2*A, A(n) = s(n)*Pi + (2)^n*A where s(n) = (1)^(n1) * a(n) [1orthic triangle = the orthic triangle of ABC, northic triangle = the orthic triangle of the (n1)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 pairs of consecutive terms give all powers of 2 in increasing order.  Amarnath Murthy, Aug 15 2002
Excess clockwise moves (over counterclockwise) needed to move a tower of size n to the clockwise peg is (1)^n*(2^n  (1)^n)/3; a(n) is 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 + 28 + 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(n1) 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=2*k (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 nth entry (n > 1) of the sequence is equal to the 2,2entry of the nth 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) is the number of Motzkin (n+1)sequences whose flatsteps all occur at level 1 and whose height is less than or equal to 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 sequence 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 for 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^(n1), where b(n) is the sequence of the arithmetic means of previous two terms defined by b(n) = 1/2*(b(n1) + b(n2)) 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) satisfies A(x) = B(2*x)/2. Because b(n) converges to the limit lim (1x)*B(x) = 1/3*(b(0) + 2*b(1)) = 2/3 (for x > 1), it follows that a(n)/2^(n1) 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(n1)) = 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) = 9*x*(xc) + (c1)*(2*c+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(n1). Let A005578(n), a(n), A000975(n1) = triangle (a, b, c). Then ((Sc), (Sb), (Sa)) = (A005578(n1), a(n1), A000975(n2)). Example: (a, b, c) = (11, 11, 10) = (A005578(5), a(5), A000975(4). Then ((Sc), (Sb), (Sa)) = (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^(n1) 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) is the term (5, 1) of nth 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 threedimensional 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, 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)^(n1)*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(n1) copies of each of s and t.  Andrew Rupinski, Mar 12 2010
As a fraction: 1/88 = 0.0113636363... or 1/9898 = 0.00010103051121...  Mark Dols, 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 (A266508) generates this sequence.  Paul Muljadi, Jan 27 2011
This is a divisibility sequence.  Michael Somos, Feb 06 2011
From L. Edson Jeffery, Apr 04 2011: (Start)
Let U be the unitprimitive 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. (End)
The sequence emerges in using iterated deletion of strictly dominated strategies to establish the bestresponse 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 pcolored compositions of n. For n >= 2, 3*a(n1) equals the number of 3colored compositions of n with all parts greater than or equal to 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 ith 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 nth column. Because a(n) + a(n+1) = 2^n, then a(n+1) = Number of digits "0" among the 2^n elements of the nth column.  Michel Lagneau, Jan 11 2012
3!*a(n1) is apparently the trace of the nth power of the adjacency matrix of the complete 3graph, a 3 X 3 matrix with diagonal elements all zero and offdiagonal all ones. The offdiagonal elements for the nth 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
From Paul Curtz, Dec 11 2012: (Start)
2^n * a(n) = (1)^(n1) * a(n), which extends the sequence to negative indices: ..., 5/16, 3/8, 1/4, 1/2, 0, 1, 1, 3, 5, ...
The "autosequence" 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 higherorder 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 0's. (End)
Assign to a triangle T(n, 0) = 1 and T(n+1, 1) = n; T(r, c) = T(r1, c1) + T(r1, c2) + T(r2, c2). 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 that 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, j1) + m(i1, j1) otherwise, then m(n+1, n+1) = 3^(n1).  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 randomlygenerated infinite sequence of 1's and 2's. 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) is the top left entry of the (n1)st power of the 3 X 3 matrix [1, 1, 1, 1, 0, 0, 1, 0, 0]. a(n) is the top left entry of the (n+1)st 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(n1) + t*a(n2) 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
This is the Lucas sequence U(1, 2).  Felix P. Muga II, Mar 21 2014
sqrt(a(n+1) * a(n1)) > a(n) + 3/4 if n is even, and > a(n)  3/4 if n is odd, for n >= 2.  Richard R. Forberg, Jun 24 2014
a(n+1) counts closed walks on the end vertices of P_3 containing one loop at the middle vertex. a(n1) counts closed walks on the middle vertex of P_3 containing one loop at that vertex.  David Neil McGrath, Nov 07 2014
From César Eliud Lozada, Jan 21 2015: (Start)
Let P be a point in the plane of a triangle ABC (with sides a, b, c) and barycentric coordinates P = [x:y:z]. The Complement of P with respect to ABC is defined to be Complement(P) = [b*y + c*z : c*z + a*x : a*x + b*y].
Then, for n >= 1, Complement(Complement(...(Complement(P))..)) = (n times) =
[2*a(n1)*a*x + (2*a(n1)  (1)^n)*(b*y + c*z):
2*a(n1)*b*y + (2*a(n1)  (1)^n)*(c*z + a*x):
2*a(n1)*c*z + (2*a(n1)  (1)^n)*(a*x + b*y)]. (End)
a(n) (n >= 2) is the number of induced hypercubes of the Fibonacci cube Gamma(n2). See p. 513 of the Klavzar reference. Example: a(5) = 11. Indeed, the Fibonacci cube Gamma(3) is <> (cycle C(4) with a pendant edge) and the hypercubes are: 5 vertices, 5 edges, and 1 square.  Emeric Deutsch, Apr 07 2016
If the sequence of points {P_i(x_i, y_i)} on the cubic y = a*x^3 + b*x^2 + c*x + d has the property that the segment P_i(x_i, y_i) P_i+1(x_i+1, y_i+1) is always tangent to the cubic at P_i+1(x_i+1, y_i+1) then a(n) = 2^n*a/b*(x_(n+1)(1/2)^n*x_1).  Michael Brozinsky, Aug 01 2016
With the quantum integers defined by [n+1]_q = (q^(n+1)  q^(n1)) / (q  q^(1)), the Jacobsthal numbers are a(n+1) = (1)^n*q^n [n+1]_q with q = i * sqrt(2) for i^2 = 1, whereas the signed Mersenne numbers A000225 are given by q = sqrt(2). Cf. A239473.  Tom Copeland, Sep 05 2016
Every positive integer has a unique expression as a sum of Jacobsthal numbers in which the index of the smallest summand is odd, with a(1) and a(2) both allowed. See the L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr. reference.  Ira M. Gessel, Dec 31 2016. See A280049 for these expansions.  N. J. A. Sloane, Dec 31 2016
For n > 0, a(n) equals the number of ternary words of length n1 in which 0 and 1 avoid runs of odd lengths.  Milan Janjic, Jan 08 2017
For n > 0, a(n) equals the number of orbits of the finite group PSL(2,2^n) acting on subsets of size 4 for the 2^n+1 points of the projective line.  Paul M. Bradley, Jan 31 2017
For n > 1, number of words of length n2 over alphabet {1,2,3} such that no odd letter is followed by an odd letter.  Armend Shabani, Feb 17 2017
Also, the decimal representation of the xaxis, from the origin to the right edge, of the nth stage of growth of the twodimensional cellular automaton defined by "Rule 678", based on the 5celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. See A283641.  Robert Price, Mar 12 2017
Also the number of independent vertex sets and vertex covers in the 2 X (n2) king graph.  Eric W. Weisstein, Sep 21 2017
From César Eliud Lozada, Dec 14 2017: (Start)
Let T(0) be a triangle and let T(1) be the medial triangle of T(0), T(2) the medial triangle of T(1) and, in general, T(n) the medial triangle of T(n1). The barycentric coordinates of the first vertex of T(n) are [2*a(n1)/a(n), 1, 1], for n > 0.
Let S(0) be a triangle and let S(1) be the antimedial triangle of S(0), S(2) the antimedial triangle of S(1) and, in general, S(n) the antimedial triangle of S(n1). The barycentric coordinates of the first vertex of S(n) are [a(n+1)/a(n), 1, 1], for n > 0. (End)
a(n) is also the number of derangements in S_{n+1} with empty peak set.  Isabella Huang, Apr 01 2018
For n > 0, gcd(a(n), a(n+1)) = 1.  Kengbo Lu, Jul 27 2020
Number of 2compositions of n+1 with 1 not allowed as a part; see Hopkins & Ouvry reference.  Brian Hopkins, Aug 17 2020
The number of Hamiltonian paths of the flower snark graph of even order 2n > 2 is 12*a(n1).  Don Knuth, Dec 25 2020
When set S = {1, 2, ..., 2^n}, n>=0, then the largest subset T of S with the property that if x is in T, then 2*x is not in T, has a(n+1) elements. For example, for n = 4, #S = 16, a(5) = 11 with T = {1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16} (see Hassan Tarfaoui link, Concours Général 1991).  Bernard Schott, Feb 14 2022
a(n) is the number of words of length n over a binary alphabet whose position in the lexicographic order is one more than a multiple of three. a(3) = 3: aaa, abb, bba.  Alois P. Heinz, Apr 13 2022


REFERENCES

J. Austin and L. Schneider, Generalized Fibonacci sequences in Pythagorean triple preserving sequences, Fib. Q., 58:1 (2020), 340350.
Henri Brocard, "Propriété d'une série de triangles", Nouvelle Correspondance Mathématique, Vol. 6 (1880), 145151.
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.
Ernst Erich Jacobsthal, Fibonaccische Polynome und Kreisteilungsgleichungen, Sitzungsber. Berliner Math. Gesell. 17 (19191920), 4357.
Tanya Khovanova, "Coins and Logic", Chapter 6, The Mathematics of Various Entertaining Subjects: Volume 3 (2019), Jennifer Beineke & Jason Rosenhouse, eds. Princeton University Press, Princeton and Oxford, p. 73. ISBN: 0691182582, 9780691182582.
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.
T. Koshy and R. P. Grimaldi, Ternary words and Jacobsthal numbers, Fib. Quart., 55 (No. 2, 2017), 129136.
S. Roman, Introduction to Coding and Information Theory, Springer Verlag, 1996, 4142.
P. D. Seymour and D. J. A. Welsh, Combinatorial applications of an inequality form statistical mechanics, Math. Proc. Camb. Phil. Soc. 77 (1975), 485495. [Although Daykin et al. (1979) claim that the present sequence is studied in this article, it does not seem to be explicitly mentioned. Note that definition of logconvex in (3.1) is wrong.  N. J. A. Sloane, Dec 26 2020]
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).
Robert M. Young, "Excursions in Calculus", MAA, 1992, p. 239


LINKS

Indranil Ghosh, Table of n, a(n) for n = 0..3316 (terms 0..500 from T. D. Noe)
M. H. Albert, M. D. Atkinson, and V. Vatter, Inflations of geometric grid classes: three case studies.
JeanPaul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, and Jiemeng Zhang, Sumfree sets generated by the periodkfolding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
Joerg Arndt, Matters Computational (The Fxtbook), pp.315318
Mohammad K. Azarian, Limit of Nested Square Roots, Problem B664, Fibonacci Quarterly, Vol. 28, No. 2, May 1990, p. 182.
Mohammad K. Azarian, Solution to Problem B664, Limit of Nested Square Roots, Fibonacci Quarterly, Vol. 29, No. 2, May 1991, p. 182.
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
Paul Barry, On sequences with {1, 0, 1} Hankel transforms, arXiv preprint arXiv:1205.2565 [math.CO], 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 IntegerSequenceBased Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343385.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
K. Böhmová, C. Dalfó, and C. Huemer, On cyclic Kautz digraphs, Preprint 2016.
W. Bosma, Signed bits and fast exponentiation, J. Th. Nombres de Bordeaux, 13 no. 1 (2001), p. 2741.
G. Bowlin and M. G. Brin, Coloring Planar Graphs via Colored Paths in the Associahedra, arXiv preprint arXiv:1301.3984 [math.CO], 2013.  From N. J. A. Sloane, Feb 12 2013
Rachael Boyd and Richard Hepworth, Combinatorics of injective words for TemperleyLieb algebras, arXiv:2006.04261 [math.AT], 2020.
Paul Bradley and Peter Rowley, Orbits on ksubsets of 2transitive Simple Lietype Groups, 2014.
H. Bruhn, L. Gellert, and J. Günther, Jacobsthal numbers in generalised Petersen graphs, arXiv preprint arXiv:1503.03390 [math.CO], 2015.
H. Bruhn, L. Gellert, and J. Günther, Jacobsthal numbers in generalised Petersen graphs, Electronic Notes in Discrete Math., 2015.
L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fibonacci Quarterly 10.5 (1972), pages 499518 and 550.
Paula Catarino, Helena Campos, and Paulo Vasco. On the Mersenne sequence. Annales Mathematicae et Informaticae, 46 (2016) pp. 3753.
Miquel Cerda, Irregular triangle whose row sums are the Jacobsthal numbers
Ji Young Choi, Ternary Modified Collatz Sequences And Jacobsthal Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.7.5.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the xaxis, arXiv:1501.04750 [math.CO], 2015.
M. H. Cilasun, An Analytical Approach to ExponentRestricted Multiple Counting Sequences, arXiv preprint arXiv:1412.3265 [math.NT], 2014.
M. H. Cilasun, Generalized Multiple Counting Jacobsthal Sequences of Fermat Pseudoprimes, Journal of Integer Sequences, Vol. 19, 2016, #16.2.3.
Charles K. Cook and Michael R. Bacon, Some identities for Jacobsthal and JacobsthalLucas numbers satisfying higher order recurrence relations, Annales Mathematicae et Informaticae, 41 (2013) pp. 2739.
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), 135156.
Gesualdo Delfino and Jacopo Viti, Potts qcolor field theory and scaling random cluster model, arXiv:1104.4323 [hepth], 2011.
Karl Dilcher and Larry Ericksen, Continued fractions and Stern polynomials. Ramanujan Journal (2017). See Table 2.
Karl Dilcher and Hayley Tomkins, Square classes and divisibility properties of Stern polynomials, Integers (2018) 18, Article #A29.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, OddRule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
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 [mathph], 2012.
M. C. Firengiz and A. Dil, Generalized EulerSeidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 2132.
D. D. Frey and J. A. Sellers, Jacobsthal Numbers and Alternating Sign Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.3.
Robert Frontczak and Taras Goy, MersenneHoradam identities using generating functions, Carpathian Math. Publ. (2020) Vol. 12, No. 1, 3445.
E. M. GarcíaCaballero, S. G. Moreno, and M. P. Prophet, New Viètelike infinite products of nested radicals, Fib. Q., 52 (No. 1, 2014), 2731.
Dale Gerdemann, Triangles from (1,2) Recursion and Recursive Triangle Fragmentation from (1,2) Recursion , YouTube Videos, December 2014.
A. Goldberg and N. A. Rosenberg, Beyond 2/3 and 1/3: the complex signatures of sexbiased admixture on the X chromosome, Genetics 201 (2015), 263279.
J. Goldwasser et al., The density of ones in Pascal's rhombus, Discrete Math., 204 (1999), 231236.
Taras Goy, On determinants and permanents of some ToeplitzHessenberg matrices whose entries are Jacobsthal numbers, Eurasian Math. J. (2018) Vol. 9, No. 4, 6167.
Taras P. Goy, Jacobsthal number identities using the generalized Brioschi formula, Vasyl Stefanyk Precarpathian National University, (IvanoFrankivsk, Ukraine, 2020).
Jonny Griffiths, The Notontheline transformation, The Mathematical Gazette, 99, pp 347352 (2015).
Martin Griffiths and Alex Bramham, The Jacobsthal Numbers: Two Results and Two Questions, Fibonacci Quart. 53 (2015), no. 2, 147151.
R. K. Guy, Letters to N. J. A. Sloane, JuneAugust 1968
Richard K. Guy, Tanya Khovanova, and Julian Salazar, Conway's subprime Fibonacci sequences, arXiv:1207.5099 [math.NT], 20122014.
Lee Haehwang, Illustration of initial terms in terms of rosemary plants
Silvia Heubach, Tiling an mbyn area with squares of size up to kbyk (m<=5), preprint, published in: Congressus Numerantium 140 (1999), 4364.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi  Myths and Maths, Birkhäuser 2013. See page 56. Book's website
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and SierpinskiType Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
Brian Hopkins, Andrew V. Sills, and Thotsaporn “AEK” Thanatipanonda, and Hua Wang, Parts and subword patterns in compositions, Preprint 2015.
A. F. Horadam, Jacobsthal and Pell Curves, Fib. Quart. 26, 7983, 1988. [See J_n.]
A. F. Horadam, Jacobsthal Representation Numbers, Fib Quart. 34, 4054, 1996.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 142
Dan Ismailescu, Joehyun Kim, Kelvin Kim, and Jeewoo Lee, The largest angle bisection procedure, arXiv:1908.02749 [math.MG], 2019. See p. 17.
M. Janjić, On Linear Recurrence Equations Arising from Compositions of Positive Integers, J. Int. Seq. 18 (2015), #15.4.7.
Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.
L. E. Jeffery, Unitprimitive matrices
D. Jhala, G. P. S. Rathore, and K. Sisodiya, Some Properties of kJacobsthal Numbers with Arithmetic Indexes, Turkish Journal of Analysis and Number Theory, 2014, Vol. 2, No. 4, 119124.
Tanya Khovanova, Coins and Logic, arXiv:1801.01143 [math.HO], 2018.
Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 2013, 505522.
Masato Kobayashi, Weighted counting of Bruhat paths by shifted Rpolynomials, arXiv:1907.11802 [math.CO], 2019.
Takao Komatsu, Continued fractions associated with the topological index of the caterpillarbond graph, arXiv:1903.09986 [math.CO], 2019.
Peter J. Larcombe, Julius Fergy T. Rabago, and Eric J. Fennessey, On two derivative sequences from scaled geometric mean sequence terms, Palestine Journal of Mathematics (2018) Vol. 7(2), 397405.
KyuHwan Lee and Sejin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
E. Lemmen, J. van Duivenbode, J. L. Duarte, and E. A. Lomonova, Flexible Multilevel Converters using 4Switch Extended Commutation Cells, Emerging and Selected Topics in Power Electronics, IEEE Journal of, Volume:PP, Issue: 99, 2015.
S. L. Levine, Suppose more rabbits are born, Fib. Quart., 26 (1988), 306311.
Alan J. Macfarlane, On generating functions of some sequences of integers defined in the evolution of the cellular automaton Rule 150, Preprint 2016.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002.
B. D. McKay and I. M. Wanless, A census of small latin hypercubes, SIAM J. Discrete Math. 22, (2008) 719736.
A. Moghaddamfar and H. Tajbakhsh, More Determinant Representations for Sequences, Journal of Integer Sequences, 17 (2014), #14.5.6.
Sophie MorierGenoud, Counting Coxeter's friezes over a finite field via moduli spaces, arXiv:1907.12790 [math.CO], 2019.
F. P. Muga II, Extending the Golden Ratio and the Binetde Moivre Formula, March 2014; Preprint on ResearchGate.
Emanuele Munarini, A generalization of AndréJeannin's symmetric identity, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 98118.
G. Myerson and A. J. van der Poorten, Some problems concerning recurrence sequences, Amer. Math. Monthly 102 (1995), no. 8, 698705.
S. Northshield, Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ..., Amer. Math. Monthly, 117 (2010), 581598.
Kritkhajohn Onphaeng and Prapanpong Pongsriiam, Jacobsthal and JacobsthalLucas Numbers and Sums Introduced by Jacobsthal and Tverberg, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.6.
Ahmet Öteleş, Zekeriya Y. Karatas, and Diyar O. Mustafa Zangana, Jacobsthal Numbers and Associated Hessenberg Matrices, J. Int. Seq., Vol. 21 (2018), Article 18.2.5.
D. Panario, M. Sahin, and Q. Wang, A family of Fibonaccilike conditional sequences, INTEGERS, Vol. 13, 2013, #A78.
D. Panario, M. Sahin, Q. Wang, and W. Webb, General conditional recurrences, Applied Mathematics and Computation, Volume 243, Sep 15 2014, Pages 220231.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
M. Rahmani, The AkiyamaTanigawa matrix and related combinatorial identities, Linear Algebra and its Applications 438 (2013) 219230.  From N. J. A. Sloane, Dec 26 2012
N. A. Rosenberg, Admixture models and the breeding systems of H. S. Jennings: a GENETICS connection, Genetics 202 (2016), 913.
E. Schlemm, On the expected number of successes in a sequence of nested Bernoulli trials, arXiv preprint arXiv:1303.4979 [math.PR], 2013.
A. G. Shannon and J. V. Leyendekkers, The Golden Ratio family and the Binet equation, Notes on Number Theory and Discrete Mathematics, Vol. 21, 2015, No. 2, 3542.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Yüksel Soykan, On Summing Formulas For Generalized Fibonacci and Gaussian Generalized Fibonacci Numbers, Advances in Research (2019) Vol. 20, No. 2, 115, Article AIR.51824.
Yüksel Soykan, Generalized Fibonacci Numbers: Sum Formulas, Journal of Advances in Mathematics and Computer Science (2020) Vol. 35, No. 1, 89104.
Yüksel Soykan, Closed Formulas for the Sums of Squares of Generalized Fibonacci Numbers, Asian Journal of Advanced Research and Reports (2020) Vol. 9, No. 1, 2339, Article no. AJARR.55441.
Yüksel Soykan, A Study on Generalized Fibonacci Numbers: Sum Formulas Sum_{k=0..n} k * x^k * W_k^3 and Sum_{k=1..n} k * x^k W_k^3 for the Cubes of Terms, Earthline Journal of Mathematical Sciences (2020) Vol. 4, No. 2, 297331.
Yüksel Soykan, Erkan Taşdemir, and İnci Okumuş, On Dual Hyperbolic Numbers With Generalized Jacobsthal Numbers Components, Zonguldak Bülent Ecevit University, (Zonguldak, Turkey, 2019).
Paul K. Stockmeyer, The Pascal Rhombus and the Stealth Configuration, arXiv:1504.04404 [math.CO], 2015.
X. Sun and V. H. Moll, The padic Valuations of Sequences Counting Alternating Sign Matrices, JIS 12 (2009) 09.3.8.
Hassan Tarfaoui, Concours Général 1991  Exercice 4 (in French).
TwoYear College Math. Jnl., Review of "Jacobsthal Representation Numbers", 28 (1997), p. 76.
USA Mathematical Olympiad 2013, Problem 2 (proposed by Sam Vandervelde).
Eric Weisstein's World of Mathematics, Jacobsthal Number, Negabinary, Repunit, Rule 28.
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, Elementary cellular automaton
OEIS Wiki, Autosequence
Abdelmoumène Zekiri, Farid Bencherif, and Rachid Boumahdi, Generalization of an Identity of Apostol, J. Int. Seq., Vol. 21 (2018), Article 18.5.1.
G. B. M. Zerr, Problem 64, American Mathematical Monthly, vol. 3, no. 12, 1896 (p. 311).
Index entries for sequences related to Chebyshev polynomials.
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (1,2).
Index entries for "core" sequences
Index to sequences related to Olympiads and other Mathematical competitions.


FORMULA

a(n) = 2^(n1)  a(n1). a(n) = 2*a(n1)  (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*n1)1 for n >= 1, a(2*n+1) = 2*a(2*n)+1 for n >= 0.  Lee Haehwang, Oct 11 2002; corrected by Mario Catalani (mario.catalani(AT)unito.it), Dec 04 2002
Also a(n) is the coefficient of x^(n1) in the bivariate Fibonacci polynomials F(n)(x, y) = x*F(n1)(x, y) + y*F(n2)(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^(k1).  Paul Barry, Apr 02 2003
The ratios a(n)/2^(n1) 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(n1, i/(2*sqrt(2)))*(i*sqrt(2))^(n1) with i^2=1.  Paul Barry, Nov 17 2003
a(n+1) = Sum_{k=0..ceiling(n/2)} 2^k*binomial(nk, 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)^(n1))/3 so lim_{n>infinity} 2^n/a(n) = 3.  Gerald McGarvey, Jul 21 2004
a(n) = Sum_{k=0..n1} (1)^k*2^(nk1) = Sum_{k=0..n1}, 2^k*(1)^(nk1).  Paul Barry, Jul 30 2004
a(n+1) = Sum_{k=0..n} binomial(k, nk)*2^(nk).  Paul Barry, Oct 07 2004
a(n) = Sum_{k=0..n1} W(nk, k)*(1)^(nk)*binomial(2*k,k), W(n, k) as in A004070.  Paul Barry, Dec 17 2004
From Paul Barry, Jan 17 2005: (Start)
a(n) = Sum_{k=0..n} k*binomial(n1, (nk)/2)*(1+(1)^(n+k))*floor((2*k+1)/3).
a(n+1) = Sum_{k=0..n} k*binomial(n1, (nk)/2)*(1+(1)^(n+k))*(A042965(k)+0^k). (End)
From Paul Barry, Jan 17 2005: (Start)
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(n1) = A005578(n)^2  A000975(n1)^2. (End)
a(n+1) = Sum_{k=0..n} Sum_{j=0..n} (1)^(nj)*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 threestep recursion a(0)=0, a(1)=1, a(2)=1, a(n) = 2*a(n1) + a(n2)  2*a(n3) 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(n1).  Paul Barry, Oct 08 2005
From Paul Barry, Feb 20 2003: (Start)
a(n) = Sum_{k=0..floor(n, 3)} binomial(n, f(n1)+3*k);
a(n) = Sum_{k=0..floor(n/3)} binomial(n, f(n2)+3*k), where f(n)=A080424(n). (End)
From Miklos Kristof, Mar 07 2007: (Start)
a(2*n) = (1/3)*Product_{dn} cyclotomic(d,4).
a(2*n+1) = (1/3)*Product_{d2*n+1} cyclotomic(2*d,2). (End)
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)) = sqrt(2sqrt(2sqrt(2sqrt(...sqrt(2)))...) {with the '2' n times, n >= 0}.
Also 2*cos(2^(n)*Pi*a(n)) = sqrt(2sqrt(2sqrt(2sqrt(...sqrt(2)))...) {with the '2' n1 times, n >= 1} as well as
2*sin(2^(n)*3/2*Pi*a(n)) = sqrt(2+sqrt(2+sqrt(2+sqrt(...sqrt(2)))...) {with the '2' n times, n >= 0} and
2*cos(2^(n)*3*Pi*a(n)) = sqrt(2+sqrt(2+sqrt(2+sqrt(...sqrt(2)))...) {with the '2' n1 times, 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)=sqrt(2b(n1)).
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)=sqrt(2+c(n1)), the following formulas hold true: a(n) = 2^n/3*(1(1)^n*(12/Pi*arcsin(c(n+1)/2)); a(n) = 2^n/3*(1(1)^n*(11/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(n1)].  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 otherwise. (When using such a Kcoefficient, 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 Kcoefficient.)  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)^(nk). Philippe Deléham, Oct 26 2008
a(n) = sqrt(8*a(n1)*a(n2) + 1). E.g., sqrt(3*5*8+1) = 11, sqrt(5*11*8+1) = 21.  Giuseppe Ottonello, Jun 14 2009
Let p[i] = Fibonacci(i1) and let A be the Hessenberg matrix of order n defined by: A[i,j] = p[ji+1], (i <= j), A[i,j] = 1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n1) = det(A).  Milan Janjic, May 08 2010
a(p1) = p*A007663(n)/3 if n > 1, and a(p1) = 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 nth term in the Fibonacci sequence: The formula for the nth term in the Fibonacci sequence is F(n) = ((1+sqrt(5))^n  (1sqrt(5))^n)/(2^n*sqrt(5)). Replacing the 5's with 9's gives ((1+sqrt(9))^n  (1sqrt(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(n1) + (1 + (1)^(n1))/2.  Vladimir Shevelev, Feb 27 2012
From Sergei N. Gladkovskii, Jun 12 2012: (Start)
G.f.: x/(1x2*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, 3step).
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, 3step). (End)
a(n) = 2^k * a(nk) + (1)^(n+k)*a(k).  Paul Curtz, JeanFrançois Alcover, Dec 11 2012
a(n) = sqrt((A014551(n))^2 + (1)^(n1)*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_{k=1..n, k odd} C(n,k)*3^(k1))/2^(n1).  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)^(n1)*Sum_{k=0..n1} A135278(n1,k)*(3)^k = (2^n  (1)^n)/3 = (1)^(n1)*Sum_{k=0..n1} (2)^k. Equals (1)^(n1)*Phi(n,2), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.)  Tom Copeland, Apr 14 2014
From Peter Bala, Apr 06 2015: (Start)
a(2*n)/a(n) = A014551(n) for n >= 1; a(3*n)/a(n) = 3*A245489(n) for n >= 1.
exp( Sum_{n >= 1} a(2*n)/a(n)*x^n/n ) = Sum_{n >= 0} a(n+1)*x^n.
exp( Sum_{n >= 1} a(3*n)/a(n)*x^n/n ) = Sum_{n >= 0} A084175(n+1)*x^n.
exp( Sum_{n >= 1} a(4*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015266(n+3)*(x)^n.
exp( Sum_{n >= 1} a(5*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015287(n+4)*x^n.
exp( Sum_{n >= 1} a(6*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015305(n+5)*(x)^n.
exp( Sum_{n >= 1} a(7*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015323(n+6)*x^n.
exp( Sum_{n >= 1} a(8*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015338(n+7)*(x)^n.
exp( Sum_{n >= 1} a(9*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015356(n+8)*x^n.
exp( Sum_{n >= 1} a(10*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015371(n+9)*(x)^n. (End)
a(n) = (1(1)^n)/2 + floor((2^n)/3).  Reiner Moewald, Jun 05 2015
a(n+k)^2  A014551(k)*a(n)*a(n+k) + (2)^k*a(n)^2 = (2)^n*a(k)^2, for n >= 0 and k >= 0.  Alexander Samokrutov, Jul 21 2015
Dirichlet g.f.: (PolyLog(s,2) + (1  2^(1s))*zeta(s))/3.  Ilya Gutkovskiy, Jun 27 2016
From Yuchun Ji, Apr 08 2018: (Start)
a(m)*a(n) + a(m1)*a(n1)  2*a(m2)*a(n2) = 2^(m+n3).
a(m+n1) = a(m)*a(n) + 2*a(m1)*a(n1); a(m+n) = a(m+1)*a(n+1)  4*a(m1)*a(n1).
a(2*n1) = a(n)^2 + 2*a(n1)^2; a(2*n) = a(n+1)^2  4*a(n1)^2. (End)
a(n+4) = a(n) + 5*2^n, a(0) = 0, a(1..4) = [1,1,3,5]. That is to say, for n > 0, the ones digits of Jacobsthal numbers follow the pattern 1,1,3,5,1,1,3,5,1,1,3,5,....  Yuchun Ji, Apr 25 2019
a(n) mod 10 = A091084(n).  Alois P. Heinz, Apr 25 2019
The sequence starting with "1" is the second INVERT transform of (1, 1, 3, 5, 11, 21, 43, ...).  Gary W. Adamson, Jul 08 2019
From Kai Wang, Jan 14 2020: (Start)
a(n)^2  a(n+1)*a(n1) = (2)^(n1).
a(n)^2  a(n+r)*a(nr) = (2)^(nr)*a(r)^2.
a(m)*a(n+1)  a(m+1)*a(n) = (2)^n*a(mn).
a(mn) = (1)^n*(a(m)*A014551(n)  A014551(m)*a(n))/(2^(n+1)).
a(m+n) = (a(m)*A014551(n) + A014551(m)*a(n))/2.
A014551(n)^2  A014551(n+r)*A014551(nr) = 9*(1)^(nr1)*2^(nr)*a(r)^2 .
A014551(m)*A014551(n+1)  A014551(m+1)*A014551(n) = 9*(1)^(n1)*2^(n)*a(mn).
A014551(mn) = (1)^(n)*(A014551(m)*A014551(n)  9*a(m)*a(n))/2^(n+1).
A014551(m+n) = (A014551(m)*A014551(n) + 9*a(m)*a(n))/2.
a(n) = Sum_{i=0..n1; j=0..n1; i+2*j=n1} 2^j*((i+j)!/(i!*j!)). (End)
For n > 0, 1/(2*a(n+1)) = Sum_{m>=n} a(m)/(a(m+1)*a(m+2)).  Kai Wang, Mar 03 2020
For 4 > h >= 0, k >= 0, a(4*k+h) mod 5 = a(h) mod 5.  Kai Wang, May 07 2020
From Kengbo Lu, Jul 27 2020: (Start)
a(n) = 1 + Sum_{k=0..n1} a(k) if n odd; a(n) = Sum_{k=0..n1} a(k) if n even.
a(n) = F(n) + Sum_{k=0..n2} a(k)*F(nk1), where F denotes the Fibonacci numbers.
a(n) = b(n) + Sum_{k=0..n1} a(k)*b(nk), where b(n) is defined through b(0) = 0, b(1) = 1, b(n) = 2*b(n2).
a(n) = 1 + 2*Sum_{k=0..n2} a(k).
a(m+n) = a(m)*a(n+1) + 2*a(m1)*a(n).
a(2*n) = Sum_{i>=0, j>=0} binomial(nj1,i)*binomial(ni1,j)*2^(i+j). (End)


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 length5 ternary words with no two consecutive letters nonzero are (dots for 0's)
[ 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*z1); # Simon Plouffe in his 1992 dissertation
A001045 := proc(n)
(2^n(1)^n)/3 ;
end proc: # R. J. Mathar, Dec 18 2012


MATHEMATICA

Jacob0[n_] := (2^n  (1)^n)/3; Table[Jacob0[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 *)
CoefficientList[Series[x/(1  x  2 x^2), {x, 0, 34}], x] (* Robert G. Wilson v, Jul 21 2015 *)
Table[(2^n  (1)^n)/3, {n, 0, 20}] (* Eric W. Weisstein, Sep 21 2017 *)
Table[Abs[QBinomial[n, 1, 2]], {n, 0, 35}] (* John Keith, Jan 29 2022 *)


PROG

(PARI) a(n) = (2^n  (1)^n) / 3
(PARI) M=[1, 1, 0; 1, 0, 1; 0, 1, 1]; for(i=0, 34, print1((M^i)[2, 1], ", ")) \\ Lambert Klasen (lambert.klasen(AT)gmx.net), Jan 28 2005
(PARI) a=0; for(n=0, 34, print1(a, ", "); a=2*(an%2)+1) \\ K. Spage, Aug 22 2014
(Sage) [lucas_number1(n, 1, 2) for n in range(34)] # Zerinvary Lajos, Apr 22 2009
# Alternatively:
a = BinaryRecurrenceSequence(1, 2)
[a(n) for n in (0..34)] # Peter Luschny, Aug 29 2016
(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^(n1)a[n1]$
A001045(n):=a[n]$
makelist(A001045(n), n, 0, 30); /* Martin Ettl, Nov 05 2012 */
(Python) # A001045.py
def A001045():
a, b = 0, 1
while True:
yield a
a, b = b, b+2*a
sequence = A001045()
[next(sequence) for i in range(20)] # David Radcliffe, Jun 26 2016
(Python) [(2**n(1)**n)//3 for n in range(40)] # Gennady Eremin, Mar 03 2022
(Magma) [n le 2 select n1 else Self(n1)+2*Self(n2): n in [1..40]]; // Vincenzo Librandi, Jun 27 2016


CROSSREFS

Partial sums of this sequence give A000975, where there are additional comments from B. E. Williams and Bill Blewett on the tie problem.
A002487(a(n)) = A000045(n).
Row sums of A059260, A156667 and A134317. Equals A026644(n2)+1 for n > 1.
a(n) = A073370(n1, 0), n >= 1 (first column of triangle).
Cf. A266508 (binary), A081857 (base 4), A147612 (characteristic function).
Cf. A000978, A000979, A019322, A066845, A105348, A130249, A130250, A130253, A005578, A002083, A113405, A138000, A064934, A003158, A175286 (Pisano periods), A147613, A156319, A002605, A000225, A052129, A014551 (companion "autosequence"), A015266, A015287, A015305, A015323, A015338, A015356, A015371, A084175, A245489, A283641.
Cf. A049883 = primes in this sequence, A107036 = indices of primes, A129738.
Cf. A091084 (mod 10), A239473, A280049.
Bisections: A002450, A007583.
Cf. A077925 (signed version).
Sequence in context: A154917 A328284 A167167 * A077925 A152046 A283642
Adjacent sequences: A001042 A001043 A001044 * A001046 A001047 A001048


KEYWORD

nonn,nice,easy,core


AUTHOR

N. J. A. Sloane


EXTENSIONS

Thanks to Don Knuth, who pointed out several missing references, including Brocard (1880), which although it was mentioned in the 1973 Handbook of Integer Sequences, was omitted from the 1995 "Encyclopedia".  N. J. A. Sloane, Dec 26 2020


STATUS

approved



