%I #89 Mar 04 2024 01:40:22
%S 0,1,4,9,20,41,84,169,340,681,1364,2729,5460,10921,21844,43689,87380,
%T 174761,349524,699049,1398100,2796201,5592404,11184809,22369620,
%U 44739241,89478484,178956969,357913940,715827881,1431655764,2863311529,5726623060,11453246121
%N Expansion of x*(1+2*x)/((1+x)*(1-x)*(1-2*x)).
%C Original name was: Generalized Jacobsthal numbers.
%C 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
%C 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
%C Also a(n) = 2*A000975(n) if n even, a(n) = 2*A000975(n) - 1 if n odd. - _Michel Lagneau_, Jan 11 2012
%C 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
%C _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
%C From _Kensuke Matsuoka_, Aug 11 2020: (Start)
%C 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.
%C 32
%C 16 8
%C 8 4 2
%C 4 2 1 2
%C 2 1 2 4 8
%C 1 2 4 8 16 32
%C From this figure, a(n) = a(n-2) + 2^n is obtained. (End)
%C 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
%H Vincenzo Librandi, <a href="/A084639/b084639.txt">Table of n, a(n) for n = 0..1000</a>
%H Sela Fried, <a href="/A026644/a026644_1.pdf">Economically solving the Tower of Hanoi puzzle</a>.
%H A. F. Horadam, <a href="http://www.fq.math.ca/Scanned/34-1/horadam2.pdf">Jacobsthal Representation Numbers</a>, Fib Quart. 34, 40-54, 1996.
%H Wolfdieter Lang, <a href="/A084639/a084639.pdf">Notes on certain inhomogeneous three term recurrences.</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2).
%F G.f.: x*(1+2*x)/((1+x)*(1-x)*(1-2*x)).
%F E.g.f.: 4*exp(2*x)/3-3*exp(x)/2+exp(-x)/6.
%F a(n) = a(n-1)+2*a(n-2)+3, a(0)=0, a(1)=1.
%F a(n) = 2^(n+2)/3+(-1)^n/6-3/2.
%F a(n) = A001045(n+2) - A000034(n).
%F a(n) = 5*a(n-2)-4*a(n-4). Cf. A084640, A101622. - _Paul Curtz_, Apr 03 2008
%F a(n) = 2*a(n-1) + a(n-2) -2*a(n-3). - _R. J. Mathar_, Jun 28 2010
%F a(n) = a(n-1)+2*a(n-2)+3, n>1. - _Gary Detlefs_, Dec 19 2010
%F a(n) = 3*a(n-1)-2*a(n-2) +(-1)^n, n>1. - _Gary Detlefs_, Dec 19 2010
%F a(n) = a(n-2) + 2^n for n >= 2. - _Kensuke Matsuoka_, Aug 11 2020
%p a:=proc(n) (2^(n+3) + (-1)^n - 9)/6 end proc: [seq(a(n), n=0..33)]; # _Wolfdieter Lang_, Jan 24 2014
%t a[0] = 0; a[1] = 1; a[n_] := a[n] = a[n - 1] + 2 a[n - 2] + 3; Array[a, 32, 0] (* Or *)
%t a[0] = 0; a[1] = 1; a[n_] := a[n] = 3 a[n - 1] - 2 a[n - 2] + (-1)^n; Array[a, 32, 0]
%t 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 *)
%o (Magma) [2^(n+2)/3+(-1)^n/6-3/2: n in [0..35]]; // _Vincenzo Librandi_, Aug 08 2011
%o (PARI) a(n)=2^(n+2)/3-if(n%2,5,4)/3 \\ _Charles R Greathouse IV_, Aug 08 2011
%o (PARI) concat(0, Vec(x*(1+2*x)/((1+x)*(1-x)*(1-2*x)) + O(x^100))) \\ _Altug Alkan_, Dec 17 2015
%Y Cf. A000975, A000225, A001045.
%Y Cf. A265747.
%K easy,nonn
%O 0,3
%A _Paul Barry_, Jun 06 2003
%E Replaced duplicate of a formula by another recurrence - _R. J. Mathar_, Jun 28 2010