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

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

Author

Paul Barry, Jun 06 2003

Keywords

• easy
• nonn

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

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Sela Fried, Economically solving the Tower of Hanoi puzzle.
• A. F. Horadam, Jacobsthal Representation Numbers, Fib Quart. 34, 40-54, 1996.
• Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
• El-Mehdi Mehiri, Saad Mneimneh, and Hacène Belbachir, The Towers of Fibonacci, Lucas, Pell, and Jacobsthal, arXiv:2502.11045 [math.CO], 2025. See p. 12.
• Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

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