cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 23 results. Next

A001045 Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer to 2^n/3.

Original entry on oeis.org

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, 11453246123
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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 (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, 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 - 2*A, 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 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-(n-1) words 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 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) 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^(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) satisfies 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) = 9*x*(x-c) + (c-1)*(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(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) is the 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, 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... - 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 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. (End)
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 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 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
From Paul Curtz, Dec 11 2012: (Start)
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 "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 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 0's. (End)
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 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, 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 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 (n-1)-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(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
This is the Lucas sequence U(1, -2). - Felix P. Muga II, Mar 21 2014
sqrt(a(n+1) * a(n-1)) -> 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(n-1) 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(n-1)*a*x + (2*a(n-1) - (-1)^n)*(b*y + c*z):
2*a(n-1)*b*y + (2*a(n-1) - (-1)^n)*(c*z + a*x):
2*a(n-1)*c*z + (2*a(n-1) - (-1)^n)*(a*x + b*y)]. (End)
a(n) (n >= 2) is the number of induced hypercubes of the Fibonacci cube Gamma(n-2). 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]A000225%20are%20given%20by%20q%20=%20sqrt(2).%20Cf.%20A239473.%20-%20_Tom%20Copeland">q = (q^(n+1) - q^(-n-1)) / (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 n-1 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 n-2 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 x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 678", based on the 5-celled 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 (n-2) 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(n-1). The barycentric coordinates of the first vertex of T(n) are [2*a(n-1)/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(n-1). 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 2-compositions 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(n-1). - 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
Named by Horadam (1988) after the German mathematician Ernst Jacobsthal (1882-1965). - Amiram Eldar, Oct 02 2023
Define the sequence u(n) = (u(n-1) + u(n-2))/u(n-3) with u(0) = 0, u(1) = 1, u(2) = u(3) = -1. Then u(4*n) = -1 + (-1)^n/a(n+1), u(4*n+1) = 2 - (-1)^n/a(n+1), u(4*n+2) = u(4*n+3) = -1. For example, a(3) = 3 and u(8) = -2/3, u(9) = 5/3, u(10) = u(11) = -1. - Michael Somos, Oct 24 2023
From Miquel A. Fiol, May 25 2024: (Start)
Also, a(n) is the number of (3-color) states of a cycle (n+1)-pole C_{n+1} with n+1 terminals (or semiedges).
For instance, for n=3, the a(3)=3 states (3-coloring of the terminals) of C_4 are
a a a a a b
a a b b a b (End)
Also, with offset 1, the cogrowth sequence of the 6-element dihedral group D3. - Sean A. Irvine, Nov 04 2024

Examples

			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 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 + ...

References

  • Jathan Austin and Lisa Schneider, Generalized Fibonacci sequences in Pythagorean triple preserving sequences, Fib. Q., 58:1 (2020), 340-350.
  • Thomas Fink and Yong 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 (1919-1920), 43-57.
  • 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, 978-0691182582.
  • Donald E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1, Eq. 13.
  • Thomas Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.
  • Steven Roman, Introduction to Coding and Information Theory, Springer Verlag, 1996, 41-42.
  • P. D. Seymour and D. J. A. Welsh, Combinatorial applications of an inequality form statistical mechanics, Math. Proc. Camb. Phil. Soc. 77 (1975), 485-495. [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 log-convex 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

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(n-2)+1 for n > 1.
a(n) = A073370(n-1, 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).

Programs

  • 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
  • Magma
    [n le 2 select n-1 else Self(n-1)+2*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Jun 27 2016
  • Maple
    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 *)
  • 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 */
  • 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*(a-n%2)+1) \\ K. Spage, Aug 22 2014
  • 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
  • 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

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) = x/((x+1)*(1-2*x)). Simon Plouffe in his 1992 dissertation
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, 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..ceiling(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->infinity} 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
From Paul Barry, Jan 17 2005: (Start)
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). (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(n-1) = A005578(n)^2 - A000975(n-1)^2. (End)
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) = 2*a(n-1) + a(n-2) - 2*a(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
From Paul Barry, Feb 20 2003: (Start)
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)=A080425(n). (End)
From Miklos Kristof, Mar 07 2007: (Start)
a(2*n) = (1/3)*Product_{d|n} cyclotomic(d,4).
a(2*n+1) = (1/3)*Product_{d|2*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(2-sqrt(2-sqrt(2-sqrt(...sqrt(2)))...) {with the '2' n times, n >= 0}.
Also 2*cos(2^(-n)*Pi*a(n)) = sqrt(2-sqrt(2-sqrt(2-sqrt(...sqrt(2)))...) {with the '2' n-1 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' n-1 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(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)=sqrt(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 otherwise. (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
Let p[i] = Fibonacci(i-1) and let A be 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_{k=1..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
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^(1-s))*zeta(s))/3. - Ilya Gutkovskiy, Jun 27 2016
From Yuchun Ji, Apr 08 2018: (Start)
a(m)*a(n) + a(m-1)*a(n-1) - 2*a(m-2)*a(n-2) = 2^(m+n-3).
a(m+n-1) = a(m)*a(n) + 2*a(m-1)*a(n-1); a(m+n) = a(m+1)*a(n+1) - 4*a(m-1)*a(n-1).
a(2*n-1) = a(n)^2 + 2*a(n-1)^2; a(2*n) = a(n+1)^2 - 4*a(n-1)^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(n-1) = (-2)^(n-1).
a(n)^2 - a(n+r)*a(n-r) = (-2)^(n-r)*a(r)^2.
a(m)*a(n+1) - a(m+1)*a(n) = (-2)^n*a(m-n).
a(m-n) = (-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(n-r) = 9*(-1)^(n-r-1)*2^(n-r)*a(r)^2 .
A014551(m)*A014551(n+1) - A014551(m+1)*A014551(n) = 9*(-1)^(n-1)*2^(n)*a(m-n).
A014551(m-n) = (-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..n-1; j=0..n-1; i+2*j=n-1} 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..n-1} a(k) if n odd; a(n) = Sum_{k=0..n-1} a(k) if n even.
a(n) = F(n) + Sum_{k=0..n-2} a(k)*F(n-k-1), where F denotes the Fibonacci numbers.
a(n) = b(n) + Sum_{k=0..n-1} a(k)*b(n-k), where b(n) is defined through b(0) = 0, b(1) = 1, b(n) = 2*b(n-2).
a(n) = 1 + 2*Sum_{k=0..n-2} a(k).
a(m+n) = a(m)*a(n+1) + 2*a(m-1)*a(n).
a(2*n) = Sum_{i>=0, j>=0} binomial(n-j-1,i)*binomial(n-i-1,j)*2^(i+j). (End)
G.f.: x/(1 - x - 2*x^2) = Sum_{n >= 0} x^(n+1) * Product_{k = 1..n} (k + 2*x)/(1 + k*x) (a telescoping series). - Peter Bala, May 08 2024
a(n) = Sum_{r>=0} F(n-2r, r), where F(n, 0) is the n-th Fibonacci number and F(n,r) = Sum_{j=1..n} F(n+1-j, r-1) F(j, r-1). - Gregory L. Simay, Aug 31 2024
From Peter Bala, Jun 27 2025: (Start)
The following are all examples of telescoping infinite products:
Product_{n >= 1} (1 + 2^n/a(2*n+2)) = 2, since 1 + 2^n/a(2*n+2) = b(n+1)/b(n), where b(n) = 2 - 3/(2^n + 1).
Product_{n >= 1} (1 - 2^n/a(2*n+2)) = 2/5, since 1 - 2^n/a(2*n+2) = c(n+1)/c(n), where c(n) = 2 + 3/(2^n - 1).
Product_{n >= 1} (1 + (-2)^n/a(2*n+2)) = 2/3, since 1 + (-2)^n/a(2*n+2) = d(n+1)/d(n), where d(n) = 2 - 1/(1 + (-2)^n).
Product_{n >= 1} (1 - (-2)^n/a(2*n+2)) = 6/5, since 1 - (-2)^n/a(2*n+2) = e(n+1)/e(n), where e(n) = 2 - 1/(1 - (-2)^n). (End)

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

A000975 a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).

Original entry on oeis.org

0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381, 174762, 349525, 699050, 1398101, 2796202, 5592405, 11184810, 22369621, 44739242, 89478485, 178956970, 357913941, 715827882, 1431655765, 2863311530, 5726623061, 11453246122
Offset: 0

Views

Author

Mira Bernstein, N. J. A. Sloane, Robert G. Wilson v, Sep 13 1996

Keywords

Comments

Might be called the "Lichtenberg sequence" after Georg Christoph Lichtenberg, who discussed it in 1769 in connection with the Chinese Rings puzzle (baguenaudier). - Andreas M. Hinz, Feb 15 2017
Number of steps to change from a binary string of n 0's to n 1's using a Gray code. - Jon Stadler (jstadler(AT)coastal.edu)
Popular puzzles such as Spin-Out and The Brain Puzzler are based on the Gray binary system and require a(n) steps to complete for some number n.
Conjecture: {a(n)} also gives all j for which A048702(j) = A000217(j); i.e., if we take the a(n)-th triangular number (a(n)^2 + a(n))/2 and multiply it by 3, we get a(n)-th even-length binary palindrome A048701(a(n)) concatenated from a(n) and its reverse. E.g., a(4) = 10, which is 1010 in binary; the tenth triangular number is 55, and 55*3 = 165 = 10100101 in binary. - Antti Karttunen, circa 1999. (This has been now proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016
Number of ways to tie a tie of n or fewer half turns, excluding mirror images. Also number of walks of length n or less on a triangular lattice with the following restrictions; given l, r and c as the lattice axes. 1. All steps are taken in the positive axis direction. 2. No two consecutive steps are taken on the same axis. 3. All walks begin with l. 4. All walks end with rlc or lrc. - Bill Blewett, Dec 21 2000
a(n) is the minimal number of vertices to be selected in a vertex-cover of the balanced tree B_n. - Sen-peng Eu, Jun 15 2002
A087117(a(n)) = A038374(a(n)) = 1 for n > 1; see also A090050. - Reinhard Zumkeller, Nov 20 2003
Intersection of A003754 and A003714; complement of A107907. - Reinhard Zumkeller, May 28 2005
Equivalently, numbers m whose binary representation is effectively, for some number k, both the lazy Fibonacci and the Zeckendorf representation of k (in which case k = A022290(m)). - Peter Munn, Oct 06 2022
a(n+1) gives row sums of Riordan array (1/(1-x), x(1+2x)). - Paul Barry, Jul 18 2005
Total number of initial 01's in all binary words of length n+1. Example: a(3) = 5 because the binary words of length 4 that start with 01 are (01)00, (01)(01), (01)10 and (01)11 and the total number of initial 01's is 5 (shown between parentheses). a(n) = Sum_{k >= 0} k*A119440(n+1, k). - Emeric Deutsch, May 19 2006
In Norway we call the 10-ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts. - Hans Isdahl, Jan 07 2008
Equals A002450 and A020988 interlaced. - Zak Seidov, Feb 10 2008
For n > 1, let B_n = the complete binary tree with vertex set V where |V| = 2^n - 1. If VC is a minimum-size vertex cover of B_n, Sen-Peng Eu points out that a(n) = |VC|. It also follows that if IS = V\VC, a(n+1) = |IS|. - K.V.Iyer, Apr 13 2009
Starting with 1 and convolved with [1, 2, 2, 2, ...] = A000295. - Gary W. Adamson, Jun 02 2009
a(n) written in base 2 is sequence A056830(n). - Jaroslav Krizek, Aug 05 2009
This is the sequence A(0, 1; 1, 2; 1) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
From Vladimir Shevelev, Jan 30 2012, Feb 13 2012: (Start)
1) Denote by {n, k} the number of permutations of 1, ..., n with the up-down index k (for definition, see comment in A203827). Then max_k{n, k} = {n, a(n)} = A000111(n).
2) a(n) is the minimal number > a(n-1) with the Hamming distance d_H(a(n-1), a(n)) = n. Thus this sequence is the Hamming analog of triangular numbers 0, 1, 3, 6, 10, ... (End)
From Hieronymus Fischer, Nov 22 2012: (Start)
Represented in binary form each term after the second one contains every previous term as a substring.
The terms a(2) = 2 and a(3) = 5 are the only primes. Proof: For even n we get a(n) = 2*(2^(2*n) - 1)/3, which shows that a(n) is even, too, and obviously a(n) > 2 for all even n > 2. For odd n we have a(n) = (2^(n+1) - 1)/3 = (2^((n+1)/2) - 1) * (2^((n+1)/2) + 1)/3. Evidently, at least one of these factors is divisible by 3, both are greater than 6, provided n > 3. Hence it follows that a(n) is composite for all odd n > 3.
Represented as a binary number, a(n+1) has exactly n prime substrings. Proof: Evidently, a(1) = 1_2 has zero and a(2) = 10_2 has 1 prime substring. Let n > 1. Written in binary, a(n+1) is 101010101...01 (if n + 1 is odd) and is 101010101...10 (if n + 1 is even) with n + 1 digits. Only the 2- and 3-digits substrings 10_2 (=2) and 101_2 (=5) are prime substrings. All the other substrings are nonprime since every substring is a previous term and all terms unequal to 2 and 5 are nonprime. For even n + 1, the number of prime substrings equal to 2 = 10_2 is (n+1)/2, and the number of prime substrings equal to 5 = 101_2 is (n-1)/2, makes a sum of n. For odd n + 1 we get n/2 for both, the number of 2's and 5's prime substrings, in any case, the sum is n. (End)
Number of different 3-colorings for the vertices of all triangulated planar polygons on a base with n+2 vertices if the colors of the two base vertices are fixed. - Patrick Labarque, Feb 09 2013
A090079(a(n)) = a(n) and A090079(m) <> a(n) for m < a(n). - Reinhard Zumkeller, Feb 16 2013
a(n) is the number of length n binary words containing at least one 1 and ending in an even number (possibly zero) of 0's. a(3) = 5 because we have: 001, 011, 100, 101, 111. - Geoffrey Critzer, Dec 15 2013
a(n) is the number of permutations of length n+1 having exactly one descent such that the first element of the permutation is an even number. - Ran Pan, Apr 18 2015
a(n) is the sequence of the last row of the Hadamard matrix H(2^n) obtained via Sylvester's construction: H(2) = [1,1;1,-1], H(2^n) = H(2^(n-1))*H(2), where * is the Kronecker product. - William P. Orrick, Jun 28 2015
Conjectured record values of A264784: a(n) = A264784(A155051(n-1)). - Reinhard Zumkeller, Dec 04 2015. (This is proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016
Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 131", based on the 5-celled von Neumann neighborhood. See A279053 for references and links. - Robert Price, Dec 05 2016
For n > 4, a(n-2) is the second-largest number in row n of A127824. - Dmitry Kamenetsky, Feb 11 2017
Conjecture: a(n+1) is the number of compositions of n with two kinds of parts, n and n', where the order of the 1 and 1' does not matter. For n=2, a(3) = 5 compositions, enumerated as follows: 2; 2'; 1,1; 1',1 = 1',1; 1',1'. - Gregory L. Simay, Sep 02 2017
Conjecture proved by recognizing the appropriate g.f. is x/(1 - x)(1 - x)(1 - 2*x^2 - 2x^3 - ...) = x/(1 - 2*x - x^2 + 2x^3). - Gregory L. Simay, Sep 10 2017
a(n) = 2^(n-1) + 2^(n-3) + 2^(n-5) + ... a(2*k -1) = A002450(k) is the sum of the powers of 4. a(2*k) = 2*A002450(k). - Gregory L. Simay, Sep 27 2017
a(2*n) = n times the string [10] in binary representation, a(2*n+1) = n times the string [10] followed with [1] in binary representation. Example: a(7) = 85 = (1010101) in binary, a(8) = 170 = (10101010) in binary. - Ctibor O. Zizka, Nov 06 2018
Except for 0, these are the positive integers whose binary expansion has cuts-resistance 1. For the operation of shortening all runs by 1, cuts-resistance is the number of applications required to reach an empty word. Cuts-resistance 2 is A329862. - Gus Wiseman, Nov 27 2019
From Markus Sigg, Sep 14 2020: (Start)
Let s(k) be the length of the Collatz orbit of k, e.g. s(1) = 1, s(2) = 2, s(3) = 5. Then s(a(n)) = n+3 for n >= 3. Proof by induction: s(a(3)) = s(5) = 6 = 3+3. For odd n >= 5 we have s(a(n)) = s(4*a(n-2)+1) = s(12*a(n-2)+4)+1 = s(3*a(n-2)+1)+3 = s(a(n-2))+2 = (n-2)+3+2 = n+3, and for even n >= 4 this gives s(a(n)) = s(2*a(n-1)) = s(a(n-1))+1 = (n-1)+3+1 = n+3.
Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)
From Gary W. Adamson, May 14 2021: (Start)
With offset 1 the sequence equals the numbers of 1's from n = 1 to 3, 3 to 7, 7 to 15, ...; of A035263; as shown below:
..1 3 7 15...
..1 0 1 1 1 0 1 0 1 0 1 1 1 0 1...
..1.....2...........5......................10...; a(n) = Sum_(k=1..2n-1)A035263(k)
.....1...........2.......................5...; as to zeros.
..1's in the Tower of Hanoi game represent CW moves On disks in the pattern:
..0, 1, 2, 0, 1, 2, ... whereas even numbered disks move in the pattern:
..0, 2, 1, 0, 2, 1, ... (End)
Except for 0, numbers that are repunits in Gray-code representation (A014550). - Amiram Eldar, May 21 2021
From Gus Wiseman, Apr 20 2023: (Start)
Also the number of nonempty subsets of {1..n} with integer median, where the median of a multiset is the middle part in the odd-length case, and the average of the two middle parts in the even-length case. For example, the a(1) = 1 through a(4) = 10 subsets are:
{1} {1} {1} {1}
{2} {2} {2}
{3} {3}
{1,3} {4}
{1,2,3} {1,3}
{2,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
The complement is counted by A005578.
For mean instead of median we have A051293, counting empty sets A327475.
For normal multisets we have A056450, strongly normal A361202.
For partitions we have A325347, strict A359907, complement A307683.
(End)
In binary form, because the sequence 10101_2... keeps repeating, one can represent a(n) = floor(0.(10)2 * 2^n). Because 0.(10)_2 = 0.(10)_2 * 4 - 2, then 0.(10)_2 = 2/3. Substituting this value in the first expression, we obtain a(n) = floor(2^(n+1)/3). This also agrees with the formula of Paul Barry, Oct 08 2005. - _Giovanni Ciriani, Mar 31 2025

Examples

			a(4)=10 since 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111 are the 10 binary strings switching 0000 to 1111.
a(3) = 1 because "lrc" is the only way to tie a tie with 3 half turns, namely, pass the business end of the tie behind the standing part to the left, bring across the front to the right, then behind to the center. The final motion of tucking the loose end down the front behind the "lr" piece is not considered a "step".
a(4) = 2 because "lrlc" is the only way to tie a tie with 4 half turns. Note that since the number of moves is even, the first step is to go to the left in front of the tie, not behind it. This knot is the standard "four in hand", the most commonly known men's tie knot. By contrast, the second most well known tie knot, the Windsor, is represented by "lcrlcrlc".
a(n) = (2^0 - 1) XOR (2^1 - 1) XOR (2^2 - 1) XOR (2^3 - 1) XOR ... XOR (2^n - 1). - _Paul D. Hanna_, Nov 05 2011
G.f. = x + 2*x^2 + 5*x^3 + 10*x^4 + 21*x^5 + 42*x^6 + 85*x^7 + 170*x^8 + ...
a(9) = 341 = 2^8 + 2^6 + 2^4 + 2^2 + 2^0 = 4^4 + 4^3 + 4^2 + 4^1 + 4^0 = A002450(5). a(10) = 682 = 2*a(9) = 2*A002450(5). - _Gregory L. Simay_, Sep 27 2017

References

  • Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.
  • Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.

Links

Crossrefs

Partial sums of A001045.
Row sums of triangle A013580.
Equals A026644/2.
Union of the bijections A002450 and A020988. - Robert G. Wilson v, Jun 09 2014
Column k=3 of A261139.
Cf. A000295, A005578, A015441, A043291, A053404, A059260, A077854, A119440, A127824, A130125, A135228, A155051, A179970, A264784.
Complement of A107907.
Row 3 of A300653.
Other sequences that relate to the binary representation of the terms: A003714, A003754, A007088, A022290, A056830, A104161, A107909.
Cf. A000120, A001511, A003242, A027383, A070939, A164707, A295235, A319416.
Cf. A005186, A033491, A153772.
Cf. A014550, A035263
Cf. A051293, A067659, A079309, A231147, A325347, A359893, A359907, A361801.

Programs

  • GAP
    List([0..35],n->(2^(n+1)-2+(n mod 2))/3); # Muniru A Asiru, Nov 01 2018
  • Haskell
    a000975 n = a000975_list !! n
a000975_list = 0 : 1 : map (+ 1)
   (zipWith (+) (tail a000975_list) (map (* 2) a000975_list))
-- Reinhard Zumkeller, Mar 07 2012
  • Magma
    [(2^(n+1) - 2 + (n mod 2))/3: n in [0..40]]; // Vincenzo Librandi, Mar 18 2015
  • Maple
    A000975 := proc(n) option remember; if n <= 1 then n else if n mod 2 = 0 then 2*A000975(n-1) else 2*A000975(n-1)+1 fi; fi; end;
seq(iquo(2^n,3),n=1..33); # Zerinvary Lajos, Apr 20 2008
f:=n-> if n mod 2 = 0 then (2^n-1)/3 else (2^n-2)/3; fi; [seq(f(n),n=0..40)]; # N. J. A. Sloane, Mar 21 2017
  • Mathematica
    Array[Ceiling[2(2^# - 1)/3] &, 41, 0]
RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == a[n - 1] + 2a[n - 2] + 1}, a, {n, 40}] (* or *)
LinearRecurrence[{2, 1, -2}, {0, 1, 2}, 40] (* Harvey P. Dale, Aug 10 2013 *)
f[n_] := Block[{exp = n - 2}, Sum[2^i, {i, exp, 0, -2}]]; Array[f, 33] (* Robert G. Wilson v, Oct 30 2015 *)
f[s_List] := Block[{a = s[[-1]]}, Append[s, If[OddQ@ Length@ s, 2a + 1, 2a]]]; Nest[f, {0}, 32] (* Robert G. Wilson v, Jul 20 2017 *)
NestList[2# + Boole[EvenQ[#]] &, 0, 39] (* Alonso del Arte, Sep 21 2018 *)
  • PARI
    {a(n) = if( n<0, 0, 2 * 2^n \ 3)}; /* Michael Somos, Sep 04 2006 */
  • PARI
    a(n)=if(n<=0,0,bitxor(a(n-1),2^n-1)) \\ Paul D. Hanna, Nov 05 2011
  • PARI
    concat(0, Vec(x/(1-2*x-x^2+2*x^3) + O(x^100))) \\ Altug Alkan, Oct 30 2015
  • PARI
    {a(n) = (4*2^n - 3 - (-1)^n) / 6}; /* Michael Somos, Jul 23 2017 */
  • Python
    def a(n): return (2**(n+1) - 2 + (n%2))//3
print([a(n) for n in range(35)]) # Michael S. Branicky, Dec 19 2021

Formula

a(n) = ceiling(2*(2^n-1)/3).
Alternating sum transform (PSumSIGN) of {2^n - 1} (A000225).
a(n) = a(n-1) + 2*a(n-2) + 1.
a(n) = 2*2^n/3 - 1/2 - (-1)^n/6.
a(n) = Sum_{i = 0..n} A001045(i), partial sums of A001045. - Bill Blewett
a(n) = n + 2*Sum_{k = 1..n-2} a(k).
G.f.: x/((1+x)*(1-x)*(1-2*x)) = x/(1-2*x-x^2+2*x^3). - Paul Barry, Feb 11 2003
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3). - Paul Barry, Feb 11 2003
a(n) = Sum_{k = 0..floor((n-1)/2)} 2^(n-2*k-1). - Paul Barry, Nov 11 2003
a(n+1) = Sum_{k=0..floor(n/2)} 2^(n-2*k); a(n+1) = Sum_{k = 0..n} Sum_{j = 0..k} (-1)^(j+k)*2^j. - Paul Barry, Nov 12 2003
(-1)^(n+1)*a(n) = Sum_{i = 0..n} Sum_{k = 1..i} k!*k* Stirling2(i, k)*(-1)^(k-1) = (1/3)*(-2)^(n+1)-(1/6)(3*(-1)^(n+1)-1). - Mario Catalani (mario.catalani(AT)unito.it), Dec 22 2003
a(n+1) = (n!/3)*Sum_{i - (-1)^i + j = n, i = 0..n, j = 0..n} 1/(i - (-1)^i)!/j!. - Benoit Cloitre, May 24 2004
a(n) = A001045(n+1) - A059841(n). - Paul Barry, Jul 22 2004
a(n) = Sum_{k = 0..n} 2^(n-k-1)*(1-(-1)^k), row sums of A130125. - Paul Barry, Jul 28 2004
a(n) = Sum_{k = 0..n} binomial(k, n-k+1)2^(n-k); a(n) = Sum_{k = 0..floor(n/2)} binomial(n-k, k+1)2^k. - Paul Barry, Oct 07 2004
a(n) = A107909(A104161(n)); A007088(a(n)) = A056830(n). - Reinhard Zumkeller, May 28 2005
a(n) = floor(2^(n+1)/3) = ceiling(2^(n+1)/3) - 1 = A005578(n+1) - 1. - Paul Barry, Oct 08 2005
Convolution of "Number of fixed points in all 231-avoiding involutions in S_n." (A059570) with "1-n" (A024000), treating the result as if offset was 0. - Graeme McRae, Jul 12 2006
a(n) = A081254(n) - 2^n. - Philippe Deléham, Oct 15 2006
Starting (1, 2, 5, 10, 21, 42, ...), these are the row sums of triangle A135228. - Gary W. Adamson, Nov 23 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), A001045(n), a(n-1)]. - Gary W. Adamson, Dec 25 2007
2^n = 2*A005578(n-1) + 2*A001045(n) + 2*a(n-2). - Gary W. Adamson, Dec 25 2007
If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*stirling2(k,j)*x^(m-k) then a(n-3) = (-1)^(n-1)*f(n,3,-2), (n >= 3). - Milan Janjic, Apr 26 2009
a(n) + A001045(n) = A166920(n). a(n) + A001045(n+2) = A051049(n+1). - Paul Curtz, Oct 29 2009
a(n) = floor(A051049(n+1)/3). - Gary Detlefs, Dec 19 2010
a(n) = round((2^(n+2)-3)/6) = floor((2^(n+1)-1)/3) = round((2^(n+1)-2)/3); a(n) = a(n-2) + 2^(n-1), n > 1. - Mircea Merca, Dec 27 2010
a(n) = binary XOR of 2^k-1 for k=0..n. - Paul D. Hanna, Nov 05 2011
E.g.f.: 2/3*exp(2*x) - 1/2*exp(x) - 1/6*exp(-x) = 2/3*U(0); U(k) = 1 - 3/(4*(2^k) - 4*(2^k)/(1+3*(-1)^k - 24*x*(2^k)/(8*x*(2^k)*(-1)^k - (k+1)/U(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011
Starting with "1" = triangle A059260 * [1, 2, 2, 2, ...] as a vector. - Gary W. Adamson, Mar 06 2012
a(n) = 2*(2^n - 1)/3, for even n; a(n) = (2^(n+1) - 1)/3 = (1/3)*(2^((n+1)/2) - 1)*(2^((n+1)/2) + 1), for odd n. - Hieronymus Fischer, Nov 22 2012
a(n) + a(n+1) = 2^(n+1) - 1. - Arie Bos, Apr 03 2013
G.f.: Q(0)/(3*(1-x)), 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
floor(a(n+2)*3/5) = A077854(n), for n >= 0. - Armands Strazds, Sep 21 2014
a(n) = (2^(n+1) - 2 + (n mod 2))/3. - Paul Toms, Mar 18 2015
a(0) = 0, a(n) = 2*(a(n-1)) + (n mod 2). - Paul Toms, Mar 18 2015
Binary: a(n) = (a(n-1) shift left 1) + (a(n-1)) NOR (...11110). - Paul Toms, Mar 18 2015
Binary: for n > 1, a(n) = 2*a(n-1) OR a(n-2). - Stanislav Sykora, Nov 12 2015
a(n) = A266613(n) - 20*2^(n-5), for n > 2. - Andres Cicuttin, Mar 31 2016
From Michael Somos, Jul 23 2017: (Start)
a(n) = -(2^n)*a(-n) for even n; a(n) = -(2^(n+1))*a(-n) + 1 for odd n.
0 = +a(n)*(+2 +4*a(n) -4*a(n+1)) + a(n+1)*(-1 +a(n+1)) for all n in Z. (End)
G.f.: (x^1+x^3+x^5+x^7+...)/(1-2*x). - Gregory L. Simay, Sep 27 2017
a(n+1) = A051049(n) + A001045(n). - Yuchun Ji, Jul 12 2018
a(n) = A153772(n+3)/4. - Markus Sigg, Sep 14 2020
a(4*k+d) = 2^(d+1)*a(4*k-1) + a(d), a(n+4) = a(n) + 2^n*10, a(0..3) = [0,1,2,5]. So the last digit is always 0,1,2,5 repeated. - Yuchun Ji, May 22 2023

Extensions

Additional comments from Barry E. Williams, Jan 10 2000

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

Original entry on oeis.org

0, 2, 10, 42, 170, 682, 2730, 10922, 43690, 174762, 699050, 2796202, 11184810, 44739242, 178956970, 715827882, 2863311530, 11453246122, 45812984490, 183251937962, 733007751850, 2932031007402, 11728124029610, 46912496118442, 187649984473770, 750599937895082
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Numbers whose binary representation is 10, n times (see A163662(n) for n >= 1). - Alexandre Wajnberg, May 31 2005
Numbers whose base-4 representation consists entirely of 2's; twice base-4 repunits. - Franklin T. Adams-Watters, Mar 29 2006
Expected time to finish a random Tower of Hanoi problem with 2n disks using optimal moves, so (since 2n is even and A010684(2n) = 1) a(n) = A060590(2n). - Henry Bottomley, Apr 05 2001
a(n) is the number of derangements of [2n + 3] with runs consisting of consecutive integers. E.g., a(1) = 10 because the derangements of {1, 2, 3, 4, 5} with runs consisting of consecutive integers are 5|1234, 45|123, 345|12, 2345|1, 5|4|123, 5|34|12, 45|23|1, 345|2|1, 5|4|23|1, 5|34|2|1 (the bars delimit the runs). - Emeric Deutsch, May 26 2003
For n > 0, also smallest numbers having in binary representation exactly n + 1 maximal groups of consecutive zeros: A087120(n) = a(n-1), see A087116. - Reinhard Zumkeller, Aug 14 2003
Number of walks of length 2n + 3 between any two diametrically opposite vertices of the cycle graph C_6. Example: a(0) = 2 because in the cycle ABCDEF we have two walks of length 3 between A and D: ABCD and AFED. - Emeric Deutsch, Apr 01 2004
From Paul Barry, May 18 2003: (Start)
Row sums of triangle using cumulative sums of odd-indexed rows of Pascal's triangle (start with zeros for completeness):
0 0
1 1
1 4 4 1
1 6 14 14 6 1
1 8 27 49 49 27 8 1 (End)
a(n) gives the position of the n-th zero in A173732, i.e., A173732(a(n)) = 0 for all n and this gives all the zeros in A173732. - Howard A. Landman, Mar 14 2010
Smallest number having alternating bit sum -n. Cf. A065359. For n = 0, 1, ..., the last digit of a(n) is 0, 2, 0, 2, ... . - Washington Bomfim, Jan 22 2011
Number of toothpicks minus 1 in the toothpick structure of A139250 after 2^n stages. - Omar E. Pol, Mar 15 2012
For n > 0 also partial sums of the odd powers of 2 (A004171). - K. G. Stier, Nov 04 2013
Values of m such that binomial(4*m + 2, m) is odd. Cf. A002450. - Peter Bala, Oct 06 2015
For a(n) > 2, values of m such that m is two steps away from a power of 2 under the Collatz iteration. - Roderick MacPhee, Nov 10 2016
a(n) is the position of the first occurrence of 2^(n+1)-1 in A020986. See the Brillhart and Morton link, pp. 856-857. - John Keith, Jan 12 2021
a(n) is the number of monotone paths in the n-dimensional cross-polytope for a generic linear orientation. See the Black and De Loera link. - Alexander E. Black, Feb 15 2023

Links

Crossrefs

Cf. A020989, A047849, A108019, A295521, A020522.

Programs

Formula

a(n) = 4*a(n-1) + 2, a(0) = 0.
a(n) = A026644(2*n).
a(n) = A007583(n) - 1 = A039301(n+1) - 2 = A083584(n-1) + 1.
E.g.f. : (2/3)*(exp(4*x)-exp(x)). - Paul Barry, May 18 2003
a(n) = A007583(n+1) - 1 = A039301(n+2) - 2 = A083584(n) + 1. - Ralf Stephan, Jun 14 2003
G.f.: 2*x/((1-x)*(1-4*x)). - R. J. Mathar, Sep 17 2008
a(n) = a(n-1) + 2^(2n-1), a(0) = 0. - Washington Bomfim, Jan 22 2011
a(n) = A193652(2*n). - Reinhard Zumkeller, Aug 08 2011
a(n) = 5*a(n-1) - 4*a(n-2) (n > 1), a(0) = 0, a(1) = 2. - L. Edson Jeffery, Mar 02 2012
a(n) = (2/3)*A024036(n). - Omar E. Pol, Mar 15 2012
a(n) = 2*A002450(n). - Yosu Yurramendi, Jan 24 2017
From Seiichi Manyama, Nov 24 2017: (Start)
Zeta_{GL(2)/F_1}(s) = Product_{k = 1..4} (s-k)^(-b(2,k)), where Sum b(2,k)*t^k = t*(t-1)*(t^2-1). That is Zeta_{GL(2)/F_1}(s) = (s-3)*(s-2)/((s-4)*(s-1)).
Zeta_{GL(2)/F_1}(s) = Product_{n > 0} (1 - (1/s)^n)^(-A295521(n)) = Product_{n > 0} (1 - x^n)^(-A295521(n)) = (1-3*x)*(1-2*x)/((1-4*x)*(1-x)) = 1 + Sum_{k > 0} a(k-1)*x^k (x=1/s). (End)
From Oboifeng Dira, May 29 2020: (Start)
a(n) = A078008(2n+1) (second bisection).
a(n) = Sum_{k=0..n} binomial(2n+1, ((n+2) mod 3)+3k). (End)
From John Reimer Morales, Aug 04 2025: (Start)
a(n) = A000302(n) - A047849(n).
a(n) = A020522(n) + A000079(n) - A047849(n). (End)

Extensions

Edited by N. J. A. Sloane, Sep 06 2006

A013609 Triangle of coefficients in expansion of (1+2*x)^n.

Original entry on oeis.org

1, 1, 2, 1, 4, 4, 1, 6, 12, 8, 1, 8, 24, 32, 16, 1, 10, 40, 80, 80, 32, 1, 12, 60, 160, 240, 192, 64, 1, 14, 84, 280, 560, 672, 448, 128, 1, 16, 112, 448, 1120, 1792, 1792, 1024, 256, 1, 18, 144, 672, 2016, 4032, 5376, 4608, 2304, 512, 1, 20, 180, 960, 3360, 8064, 13440, 15360, 11520, 5120, 1024
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

T(n,k) is the number of lattice paths from (0,0) to (n,k) with steps (1,0) and two kinds of steps (1,1). The number of paths with steps (1,0) and s kinds of steps (1,1) corresponds to the expansion of (1+s*x)^n. - Joerg Arndt, Jul 01 2011
Also sum of rows in A046816. - Lior Manor, Apr 24 2004
Also square array of unsigned coefficients of Chebyshev polynomials of second kind. - Philippe Deléham, Aug 12 2005
The rows give the number of k-simplices in the n-cube. For example, 1, 6, 12, 8 shows that the 3-cube has 1 volume, 6 faces, 12 edges and 8 vertices. - Joshua Zucker, Jun 05 2006
Triangle whose (i, j)-th entry is binomial(i, j)*2^j.
With offset [1,1] the triangle with doubled numbers, 2*a(n,m), enumerates sequences of length m with nonzero integer entries n_i satisfying sum(|n_i|) <= n. Example n=4, m=2: [1,3], [3,1], [2,2] each in 2^2=4 signed versions: 2*a(4,2) = 2*6 = 12. The Sum over m (row sums of 2*a(n,m)) gives 2*3^(n-1), n >= 1. See the W. Lang comment and a K. A. Meissner reference under A024023. - Wolfdieter Lang, Jan 21 2008
n-th row of the triangle = leftmost column of nonzero terms of X^n, where X = an infinite bidiagonal matrix with (1,1,1,...) in the main diagonal and (2,2,2,...) in the subdiagonal. - Gary W. Adamson, Jul 19 2008
Numerators of a matrix square-root of Pascal's triangle A007318, where the denominators for the n-th row are set to 2^n. - Gerald McGarvey, Aug 20 2009
From Johannes W. Meijer, Sep 22 2010: (Start)
The triangle sums (see A180662 for their definitions) link the Pell-Jacobsthal triangle, whose mirror image is A038207, with twenty-four different sequences; see the crossrefs.
This triangle may very well be called the Pell-Jacobsthal triangle in view of the fact that A000129 (Kn21) are the Pell numbers and A001045 (Kn11) the Jacobsthal numbers.
(End)
T(n,k) equals the number of n-length words on {0,1,2} having n-k zeros. - Milan Janjic, Jul 24 2015
T(n-1,k-1) is the number of 2-compositions of n with zeros having k positive parts; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 16 2020
T(n,k) is the number of chains 0=x_0Geoffrey Critzer, Oct 01 2022
Excluding the initial 1, T(n,k) is the number of k-faces of a regular n-cross polytope. See A038207 for n-cube and A135278 for n-simplex. - Mohammed Yaseen, Jan 14 2023

Examples

			Triangle begins:
  1;
  1,  2;
  1,  4,   4;
  1,  6,  12,    8;
  1,  8,  24,   32,   16;
  1, 10,  40,   80,   80,    32;
  1, 12,  60,  160,  240,   192,    64;
  1, 14,  84,  280,  560,   672,   448,    128;
  1, 16, 112,  448, 1120,  1792,  1792,   1024,    256;
  1, 18, 144,  672, 2016,  4032,  5376,   4608,   2304,    512;
  1, 20, 180,  960, 3360,  8064, 13440,  15360,  11520,   5120,  1024;
  1, 22, 220, 1320, 5280, 14784, 29568,  42240,  42240,  28160, 11264,  2048;
  1, 24, 264, 1760, 7920, 25344, 59136, 101376, 126720, 112640, 67584, 24576, 4096;
From _Peter Bala_, Apr 20 2012: (Start)
The triangle can be written as the matrix product A038207*(signed version of A013609).
  |.1................||.1..................|
  |.2...1............||-1...2..............|
  |.4...4...1........||.1..-4...4..........|
  |.8..12...6...1....||-1...6...-12...8....|
  |16..32..24...8...1||.1..-8....24.-32..16|
  |..................||....................|
(End)

References

  • B. N. Cyvin et al., Isomer enumeration of unbranched catacondensed polygonal systems with pentagons and heptagons, Match, No. 34 (Oct 1996), pp. 109-121.
  • G. Hotz, Zur Reduktion von Schaltkreispolynomen im Hinblick auf eine Verwendung in Rechenautomaten, El. Datenverarbeitung, Folge 5 (1960), pp. 21-27.

Links

Crossrefs

Cf. A007318, A013610, etc.
Appears in A167580 and A167591. - Johannes W. Meijer, Nov 23 2009
From Johannes W. Meijer, Sep 22 2010: (Start)
Triangle sums (see the comments): A000244 (Row1); A000012 (Row2); A001045 (Kn11); A026644 (Kn12); 4*A011377 (Kn13); A000129 (Kn21); A094706 (Kn22); A099625 (Kn23); A001653 (Kn3); A007583 (Kn4); A046717 (Fi1); A007051 (Fi2); A077949 (Ca1); A008998 (Ca2); A180675 (Ca3); A092467 (Ca4); A052942 (Gi1); A008999 (Gi2); A180676 (Gi3); A180677 (Gi4); A140413 (Ze1); A180678 (Ze2); A097117 (Ze3); A055588 (Ze4).
(End)
Cf. A024023, A038207, A046816, A105728, A115068, A135278, A171977, A180662.
T(2n,n) gives A059304.

Programs

  • Haskell
    a013609 n = a013609_list !! n
a013609_list = concat $ iterate ([1,2] *) [1]
instance Num a => Num [a] where
   fromInteger k = [fromInteger k]
   (p:ps) + (q:qs) = p + q : ps + qs
   ps + qs         = ps ++ qs
   (p:ps) * qs'@(q:qs) = p * q : ps * qs' + [p] * qs
    *                = []
-- Reinhard Zumkeller, Apr 02 2011
  • Haskell
    a013609 n k = a013609_tabl !! n !! k
a013609_row n = a013609_tabl !! n
a013609_tabl = iterate (\row -> zipWith (+) ([0] ++ row) $
                                zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Jul 22 2013, Feb 27 2013
  • Magma
    [2^k*Binomial(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Sep 17 2021
  • Maple
    bin2:=proc(n,k) option remember; if k<0 or k>n then 0 elif k=0 then 1 else 2*bin2(n-1,k-1)+bin2(n-1,k); fi; end; # N. J. A. Sloane, Jun 01 2009
  • Mathematica
    Flatten[Table[CoefficientList[(1 + 2*x)^n, x], {n, 0, 10}]][[1 ;; 59]] (* Jean-François Alcover, May 17 2011 *)
BinomialROW[n_, k_, t_] := Sum[Binomial[n, k]*Binomial[k, j]*(-1)^(k - j)*t^j, {j, 0, k}]; Column[Table[BinomialROW[n, k, 3], {n, 0, 10}, {k, 0, n}], Center] (* Kolosov Petro, Jan 28 2019 *)
  • Maxima
    a(n,k):=coeff(expand((1+2*x)^n),x^k);
create_list(a(n,k),n,0,6,k,0,n); /* Emanuele Munarini, Nov 21 2012 */
  • PARI
    /* same as in A092566 but use */
steps=[[1,0], [1,1], [1,1]]; /* note double [1,1] */
/* Joerg Arndt, Jul 01 2011 */
  • Sage
    flatten([[2^k*binomial(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Sep 17 2021

Formula

G.f.: 1 / (1 - x*(1+2*y)).
T(n,k) = 2^k*binomial(n,k).
T(n,k) = 2*T(n-1,k-1) + T(n-1,k). - Jon Perry, Nov 22 2005
Row sums are 3^n = A000244(n). - Joerg Arndt, Jul 01 2011
T(n,k) = Sum_{i=n-k..n} C(i,n-k)*C(n,i). - Mircea Merca, Apr 28 2012
E.g.f.: exp(2*y*x + x). - Geoffrey Critzer, Nov 12 2012
Riordan array (x/(1 - x), 2*x/(1 - x)). Exp(2*x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(2*x)*(1 + 6*x + 12*x^2/2! + 8*x^3/3!) = 1 + 8*x + 40*x^2/2! + 160*x^3/3! + 560*x^4/4! + .... The same property holds more generally for Riordan arrays of the form (f(x), 2*x/(1 - x)). - Peter Bala, Dec 21 2014
T(n,k) = Sum_{j=0..k} (-1)^(k-j) * binomial(n,k) * binomial(k,j) * 3^j. - Kolosov Petro, Jan 28 2019
T(n,k) = 2*(n+1-k)*T(n,k-1)/k, T(n,0) = 1. - Alexander R. Povolotsky, Oct 08 2023
For n >= 1, GCD(T(n,1), ..., T(n,n)) = GCD(T(n,1),T(n,n)) = GCD(2*n,2^n) = A171977(n). - Pontus von Brömssen, Nov 01 2024

A026637 Triangular array T read by rows: T(n,0) = T(n,n) = 1 for n >= 0, T(n,1) = T(n,n-1) = floor((3*n-1)/2) for n >= 1, otherwise T(n,k) = T(n-1,k-1) + T(n-1,k) for 2 <= k <= n-2, n >= 4.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 5, 8, 5, 1, 1, 7, 13, 13, 7, 1, 1, 8, 20, 26, 20, 8, 1, 1, 10, 28, 46, 46, 28, 10, 1, 1, 11, 38, 74, 92, 74, 38, 11, 1, 1, 13, 49, 112, 166, 166, 112, 49, 13, 1, 1, 14, 62, 161, 278, 332, 278, 161, 62, 14, 1, 1, 16, 76, 223, 439, 610, 610, 439, 223, 76, 16, 1
Offset: 0

Views

Author

Clark Kimberling

Keywords

Comments

T(n, k) = number of paths from (0, 0) to (n-k, k) in directed graph having vertices (i, j) and edges (i, j)-to-(i+1, j) and (i, j)-to-(i, j+1) for i, j >= 0 and edges (i, j)-to-(i+1, j+1) for i=0, j >= 1 and odd and for j=0, i >= 1 and odd.
See A228053 for a sequence with many terms in common with this one. - T. D. Noe, Aug 07 2013

Examples

			Triangle begins as:
  1;
  1,  1;
  1,  2,  1;
  1,  4,  4,   1;
  1,  5,  8,   5,   1;
  1,  7, 13,  13,   7,   1;
  1,  8, 20,  26,  20,   8,   1;
  1, 10, 28,  46,  46,  28,  10,   1;
  1, 11, 38,  74,  92,  74,  38,  11,  1;
  1, 13, 49, 112, 166, 166, 112,  49, 13,  1;
  1, 14, 62, 161, 278, 332, 278, 161, 62, 14,  1;

Links

Crossrefs

Cf. A026638, A026639, A026640, A026641, A026642, A026643, A026644.
Cf. A026966, A026967, A026968, A026969, A026970, A228053.
Sums include: A000007 (alternating sign row), A026644 (row), A026645, A026646, A026647 (diagonal).

Programs

  • Haskell
    a026637 n k = a026637_tabl !! n !! k
a026637_row n = a026637_tabl !! n
a026637_tabl = [1] : [1,1] : map (fst . snd)
   (iterate f (0, ([1,2,1], [0,1,1,0]))) where
   f (i, (xs, ws)) = (1 - i,
     if i == 1 then (ys, ws) else (zipWith (+) ys ws, ws'))
        where ys = zipWith (+) ([0] ++ xs) (xs ++ [0])
              ws' = [0,1,0,0] ++ drop 2 ws
-- Reinhard Zumkeller, Aug 08 2013
  • Magma
    function T(n,k) // T = A026637
   if k eq 0 or k eq n then return 1;
   elif k eq 1 or k eq n-1 then return Floor((3*n-1)/2);
   else return T(n-1, k) + T(n-1, k-1);
   end if;
end function;
[T(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Jun 28 2024
  • Maple
    A026637 := proc(n,k)
      option remember;
      if k=0 or k=n then
        1
    elif k=1 or k=n-1 then
        floor((3*n-1)/2) ;
    elif k <0 or k > n then
        0;
    else
        procname(n-1,k-1)+procname(n-1,k) ;
    end if;
end proc: # R. J. Mathar, Apr 26 2015
  • Mathematica
    T[n_, k_] := T[n, k] = Which[k == 0 || k == n, 1, k == 1 || k == n-1, Floor[(3n-1)/2], k < 0 || k > n, 0, True, T[n-1, k-1] + T[n-1, k]];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 30 2018 *)
  • SageMath
    def T(n,k): # T = A026637
    if k==0 or k==n: return 1
    elif k==1 or k==n-1: return ((3*n-1)//2)
    else: return T(n-1, k) + T(n-1, k-1)
flatten([[T(n,k) for k in range(n+1)] for n in range(16)]) # G. C. Greubel, Jun 28 2024

Formula

From G. C. Greubel, Jun 28 2024: (Start)
T(n, n-k) = T(n, k).
T(2*n-1, n-1) = A026641(n), n >= 1.
Sum_{k=0..n} T(n, k) = A026644(n).
Sum_{k=0..n} (-1)^k*T(n, k) = A000007(n). (End)

A084639 Expansion of x*(1+2*x)/((1+x)*(1-x)*(1-2*x)).

Original entry on oeis.org

0, 1, 4, 9, 20, 41, 84, 169, 340, 681, 1364, 2729, 5460, 10921, 21844, 43689, 87380, 174761, 349524, 699049, 1398100, 2796201, 5592404, 11184809, 22369620, 44739241, 89478484, 178956969, 357913940, 715827881, 1431655764, 2863311529, 5726623060, 11453246121
Offset: 0

Views

Author

Paul Barry, Jun 06 2003

Keywords

Comments

Original name was: Generalized Jacobsthal numbers.
This is the sequence A(0,1;1,2;3) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
Entries correspond to value bound adjustment for an N-bit string having M bits set and a(n+1) bit transitions. Wolfram Alpha can easily generate an entry. a(5)=41 stems from input as 1111110_2 - 1010101_2. The subtraction pattern alternates (begins at 1), and bit count is ptr+2 both terms, with the lead term having only its LSB clear. - Bill McEachen, Jul 15 2011
Also a(n) = 2*A000975(n) if n even, a(n) = 2*A000975(n) - 1 if n odd. - Michel Lagneau, Jan 11 2012
In the above comment by Bill McEachen the binary pattern (in an obvious notation) is for even n 1^(n+1)0 - (10)^((n+2)/2) and for odd n 1^(n+1)0 - (10)^((n+1)/2)1. That is for even n a(n) = sum(2^k, k=1..(n+1)) - sum(2^(2*k-1), k=1..(n+2)/2) = (2^(n+2) - 4)/3, and for odd n a(n) = sum(2^k , k=1..(n+1)) - sum(2^(2*k), k=0..(n+1)/2) = (2^(n+2) - 5)/3. This checks with the formula a(n) = (2^(n+3) + (-1)^n - 9)/6 given below. After a correspondence with Bill McEachen. - Wolfdieter Lang, Jan 24 2014
Michel Lagneau's comment above is equal to the fact that a(n) = A000975(n)-1, or in other words, this sequence gives the partial sums of Jacobsthal sequence, starting from its second 1, A001045(2). From this also follows that this sequence gives the positions of repunits in "Jacobsthal greedy base", A265747. - Antti Karttunen, Dec 17 2015
From Kensuke Matsuoka, Aug 11 2020: (Start)
This sequence is the sum of diagonally arranged powers of 2 repeated in an L shape. For example, a(1)=1, a(2) = 4, a(3)=9, a(4)= 20, a(5)=41, a(6)=84 are obtained from the figure below.
32
16 8
8 4 2
4 2 1 2
2 1 2 4 8
1 2 4 8 16 32
From this figure, a(n) = a(n-2) + 2^n is obtained. (End)
For n > 0, also the total distance that the disks travel from the leftmost peg to the middle peg in the Tower of Hanoi puzzle, in the unique solution with 2^n - 1 moves (see links). - Sela Fried, Dec 17 2023

Links

Crossrefs

Cf. A000975, A000225, A001045.
Cf. A265747.

Programs

  • Magma
    [2^(n+2)/3+(-1)^n/6-3/2: n in [0..35]]; // Vincenzo Librandi, Aug 08 2011
  • Maple
    a:=proc(n) (2^(n+3) + (-1)^n - 9)/6 end proc: [seq(a(n), n=0..33)]; # Wolfdieter Lang, Jan 24 2014
  • Mathematica
    a[0] = 0; a[1] = 1; a[n_] := a[n] = a[n - 1] + 2 a[n - 2] + 3; Array[a, 32, 0] (* Or *)
a[0] = 0; a[1] = 1; a[n_] := a[n] = 3 a[n - 1] - 2 a[n - 2] + (-1)^n; Array[a, 32, 0]
CoefficientList[Series[x*(1+2*x)/((1+x)*(1-x)*(1-2*x)),{x,0,40}],x] (* or *) LinearRecurrence[{2,1,-2},{0,1,4},40]  (* Vladimir Joseph Stephan Orlovsky, Jan 30 2012 *)
  • PARI
    a(n)=2^(n+2)/3-if(n%2,5,4)/3 \\ Charles R Greathouse IV, Aug 08 2011
  • PARI
    concat(0, Vec(x*(1+2*x)/((1+x)*(1-x)*(1-2*x)) + O(x^100))) \\ Altug Alkan, Dec 17 2015
  • Python
    def A084639(n): return (4<Chai Wah Wu, Apr 25 2025

Formula

G.f.: x*(1+2*x)/((1+x)*(1-x)*(1-2*x)).
E.g.f.: 4*exp(2*x)/3-3*exp(x)/2+exp(-x)/6.
a(n) = a(n-1)+2*a(n-2)+3, a(0)=0, a(1)=1.
a(n) = 2^(n+2)/3+(-1)^n/6-3/2.
a(n) = A001045(n+2) - A000034(n).
a(n) = 5*a(n-2)-4*a(n-4). Cf. A084640, A101622. - Paul Curtz, Apr 03 2008
a(n) = 2*a(n-1) + a(n-2) -2*a(n-3). - R. J. Mathar, Jun 28 2010
a(n) = a(n-1)+2*a(n-2)+3, n>1. - Gary Detlefs, Dec 19 2010
a(n) = 3*a(n-1)-2*a(n-2) +(-1)^n, n>1. - Gary Detlefs, Dec 19 2010
a(n) = a(n-2) + 2^n for n >= 2. - Kensuke Matsuoka, Aug 11 2020

Extensions

Replaced duplicate of a formula by another recurrence - R. J. Mathar, Jun 28 2010

A026642 a(n) = A026637(2*n-1, n-2).

Original entry on oeis.org

1, 7, 28, 112, 439, 1711, 6652, 25846, 100450, 390670, 1520764, 5925718, 23112931, 90239407, 352654084, 1379410438, 5400188206, 21157958962, 82959736504, 325514137048, 1278093308806, 5021436970822, 19740128055928
Offset: 2

Views

Author

Clark Kimberling

Keywords

Links

Crossrefs

Cf. A026637, A026638, A026639, A026640, A026641, A026643, A026644.
Cf. A026645, A026646, A026647, A026966, A026967, A026968, A026969.
Cf. A026970.

Programs

  • Magma
    [n le 2 select 7^(n-1) else ((7*n^2+3*n+2)*Self(n-1) + 2*n*(2*n+1)*Self(n-2))/(2*(n-1)*(n+2)): n in [1..40]]; // G. C. Greubel, Jul 01 2024
  • Mathematica
    a[n_]:= a[n]= If[n<4, 7^(n-2), ((7*n^2-11*n+6)*a[n-1] + 2*(n-1)*(2*n- 1)*a[n-2])/(2*(n-2)*(n+1))];
Table[a[n], {n,2,40}] (* G. C. Greubel, Jul 01 2024 *)
  • SageMath
    @CachedFunction
def a(n): # a = A026642
    if n<4: return 7^(n-2)
    else: return ((7*n^2-11*n+6)*a(n-1) + 2*(n-1)*(2*n-1)*a(n-2))/(2*(n-2)*(n+1))
[a(n) for n in range(2,41)] # G. C. Greubel, Jul 01 2024

Formula

a(n) = ( (7*n^2 - 11*n + 6)*a(n-1) + 2*(n-1)*(2*n-1)*a(n-2) )/(2*(n-2)*(n+1)), n >= 4. - G. C. Greubel, Jul 01 2024

A026638 a(n) = A026637(2*n, n).

Original entry on oeis.org

1, 2, 8, 26, 92, 332, 1220, 4538, 17036, 64412, 244928, 935684, 3588392, 13806704, 53271548, 206040506, 798600332, 3101109164, 12062148368, 46986821516, 183276382472, 715748620424, 2798274135368, 10951009023716, 42895901012792, 168167959150232, 659793819847040
Offset: 0

Views

Author

Clark Kimberling

Keywords

Links

Crossrefs

Cf. A026637, A026639, A026640, A026642, A026643, A026644, A026645.
Cf. A026646, A026647, A026966, A026967, A026968, A026969, A026970.

Programs

  • Magma
    [1] cat [n le 2 select 2^(2*n-1) else ((7*n-4)*Self(n-1) + 2*(2*n-1)*Self(n-2))/(2*n): n in [1..40]]; // G. C. Greubel, Jul 01 2024
  • Mathematica
    CoefficientList[Series[1/(2+x)+3/((2+x)*Sqrt[1-4*x])-1,{x,0,20}],x] (* Vaclav Kotesovec, Oct 21 2012 *)
  • PARI
    my(x='x+O('x^66)); Vec( 1/(2+x)+3/((2+x)*sqrt(1-4*x))-1 ) \\ Joerg Arndt, May 04 2013
  • SageMath
    @CachedFunction
def a(n): # a = A026638
    if n<3: return 2^(n*(n+1)/2)
    else: return ((7*n-4)*a(n-1) + 2*(2*n-1)*a(n-2))/(2*n)
[a(n) for n in range(41)] # G. C. Greubel, Jul 01 2024

Formula

From Vaclav Kotesovec, Oct 21 2012: (Start)
G.f.: (3 - (x+1)*sqrt(1-4*x))/((x+2)*sqrt(1-4*x)).
Recurrence: 2*n*a(n) = (7*n-4)*a(n-1) + 2*(2*n-1)*a(n-2).
a(n) ~ 2^(2*n+2)/(3*sqrt(Pi*n)) (End)

A026639 a(n) = A026637(2*n, n-1).

Original entry on oeis.org

1, 5, 20, 74, 278, 1049, 3980, 15170, 58052, 222914, 858512, 3314960, 12829070, 49748705, 193259660, 751954250, 2929965020, 11431262390, 44651369720, 174597927740, 683388447260, 2677230376490, 10496941482680, 41188078562324
Offset: 1

Views

Author

Clark Kimberling

Keywords

Links

Crossrefs

Cf. A026637, A026638, A026640, A026641, A026642, A026643, A026644.
Cf. A026645, A026646, A026647, A026966, A026967, A026968, A026969.
Cf. A026970.

Programs

  • Magma
    [1] cat [n le 2 select 5*(3*n-2) else ((7*n^2+10*n+4)*Self(n-1) + 2*(2*n+1)*(n+1)*Self(n-2))/(2*n*(n+2)): n in [1..40]]; // G. C. Greubel, Jul 01 2024
  • Mathematica
    a[n_]:= a[n]= If[n<4, (5*4^(n-1) -Boole[n==1])/4, ((7*n^2-4*n+1)*a[n- 1] +2*n*(2*n-1)*a[n-2])/(2*(n^2-1))];
Table[a[n], {n,40}] (* G. C. Greubel, Jul 01 2024 *)
  • SageMath
    @CachedFunction
def a(n): # a = A026639
    if n<4: return (5*4^(n-1) - 0^(n-1))/4
    else: return ((7*n^2 - 4*n + 1)*a(n-1) + 2*n*(2*n-1)*a(n-2))/(2*(n^2-1))
[a(n) for n in range(1,41)] # G. C. Greubel, Jul 01 2024

Formula

a(n) = ((7*n^2 - 4*n + 1)*a(n-1) + 2*n*(2*n-1)*a(n-2))/(2*(n^2-1)), with a(0) = 1, a(1) = 5, a(2) = 20. - G. C. Greubel, Jul 01 2024

A026640 a(n) = A026637(2*n, n-2).

Original entry on oeis.org

1, 8, 38, 161, 662, 2672, 10676, 42398, 167756, 662252, 2610758, 10283861, 40490702, 159394424, 627456188, 2470223186, 9726696572, 38308366784, 150916209308, 594704861546, 2344206594332, 9243186573248, 36456892635848
Offset: 2

Views

Author

Clark Kimberling

Keywords

Links

Crossrefs

Cf. A026637, A026638, A026639, A026641, A026642, A026643, A026644.
Cf. A026645, A026646, A026647, A026966, A026967, A026968, A026969.
Cf. A026970.

Programs

  • Magma
    [1] cat [n le 2 select 4^(n+1) -3^(n+1) +1 else ((7*n^2+24*n+24 )*Self(n-1) + 2*(2*n+3)*(n+2)*Self(n-2))/(2*n*(n+4)): n in [1..40]]; // G. C. Greubel, Jul 01 2024
  • Mathematica
    a[n_]:= a[n]= If[n<5, 4^(n-1) -3^(n-1) +1 -Boole[n==2], ((7*n^2 -4*n + 4)*a[n-1] +2*n*(2*n-1)*a[n-2])/(2*(n-2)*(n+2))];
Table[a[n], {n,2,40}] (* G. C. Greubel, Jul 01 2024 *)
  • SageMath
    @CachedFunction
def a(n): # a = A026640
    if n<5: return 4^(n-1) -3^(n-1) +1 -int(n==2)
    else: return ((7*n^2-4*n+4)*a(n-1) + 2*n*(2*n-1)*a(n-2))/(2*(n-2)*(n+2))
[a(n) for n in range(2,41)] # G. C. Greubel, Jul 01 2024

Formula

a(n) = ((7*n^2 - 4*n + 4)*a(n-1) + 2*n*(2*n-1)*a(n-2))/(2*(n-2)*(n+2)), n >= 5. - G. C. Greubel, Jul 01 2024
Showing 1-10 of 23 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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