A094373 Expansion of (1-x-x^2)/((1-x)*(1-2*x)).

1, 2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825, 2147483649, 4294967297, 8589934593

Offset: 0

Author

Paul Barry, Apr 28 2004

Keywords

• easy
• nonn

Comments

Partial sum of 1,1,1,2,4,8,...

Binomial transform of abs(A073097).

Binomial transform is A094374.

Partial sums are in A006127. - Paul Barry, Aug 05 2004

An elephant sequence, see A175654. For the corner squares four A[5] vectors, with decimal values 2, 8, 32 and 128, lead to this sequence. For the central square these vectors lead to the companion sequence A011782. - Johannes W. Meijer, Aug 15 2010

This sequence has a(0) = 1 and for all n > 0, a(n) = 2^(n-1)+1. Consequently 2*a(n) >= a(n+1) for all n > 0 and the sequence is complete. - Frank M Jackson, Jan 29 2012

Row lengths of the triangle in A198069. - Reinhard Zumkeller, May 26 2013

Take A007843 and count the repeated values. The result is 1,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,.... Build a third sequence, where a(1) = 1 and a(n) equals the length (greater than 1) of the shortest palindromic subsequence of consecutive terms of the second sequence starting with a(n) of the second sequence. The third sequence starts 1,3,5,3,9,3,5,3,17,3,5,3,9,3,5,3,33,.... Conjecturally, in the third sequence: (1) the indices of the first occurrence of each value form the present sequence and (2) for n>1, a(n) is in the a(n-1)-th position. - Ivan N. Ianakiev, Aug 20 2019

Examples

			G.f. = 1 + 2*x + 3*x^2 + 5*x^3 + 9*x^4 + 17*x^5 + 33*x^6 + 65*x^7 + ...
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Eric Weisstein, Complete Sequence.
• Index entries for linear recurrences with constant coefficients, signature (3,-2).

Crossrefs

Apart from the initial 1, identical to A000051.

Cf. A135225.

Column k=1 of A152977.

Row n=2 of A238016.

Programs

GAP

a:=[2,3];; for n in [3..40] do a[n]:=3*a[n-1]-2*a[n-2]; od; Concatenation([1], a); # G. C. Greubel, Nov 06 2019

Magma

[(2^n-0^n)/2+1: n in [0..40]]; // Vincenzo Librandi, Jun 10 2011

Magma

R:=PowerSeriesRing(Integers(), 35); Coefficients(R!( (1-x-x^2)/((1-x)*(1-2*x)))); // Marius A. Burtea, Oct 25 2019

Maple

1, seq((2^n - 0^n)/2 +1, n=1..40); # G. C. Greubel, Nov 06 2019

Mathematica

CoefficientList[Series[(1-x-x^2)/((1-x)*(1-2*x)), {x, 0, 40}], x] (* or *) Join[{1}, LinearRecurrence[{3, -2}, {2, 3}, 40]] (* Vladimir Joseph Stephan Orlovsky, Jan 22 2012 *)
a[ n_]:= If[n<0, 0, 1 + Quotient[2^n, 2]]; (* Michael Somos, May 26 2014 *)
a[ n_]:= SeriesCoefficient[(1-x-x^2)/((1-x)(1-2x)), {x, 0, n}]; (* Michael Somos, May 26 2014 *)
LinearRecurrence[{3,-2},{1,2,3},40] (* Harvey P. Dale, Aug 09 2015 *)

PARI

a(n)=2^n\2+1 \\ Charles R Greathouse IV, Apr 05 2013

PARI

Vec((1-x-x^2)/((1-x)*(1-2*x))+O(x^40)) \\ Charles R Greathouse IV, Apr 05 2013

Sage

[(2^n - 0^n)/2 + 1 for n in (0..40)] # G. C. Greubel, Nov 06 2019

Formula

a(n) = (2^n - 0^n)/2 + 1.

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

a(2*n) = 2*a(2*n-1) - 1, n>0.

Row sums of triangle A135225. - Gary W. Adamson, Nov 23 2007

a(n) = A131577(n) + 1. - Paul Curtz, Aug 07 2008

a(n) = 2*a(n-1) - 1 for n>1, a(0)=1, a(1)=2. - Philippe Deléham, Sep 25 2009

E.g.f.: exp(x)*(1 + sinh(x)). - Arkadiusz Wesolowski, Aug 13 2012

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

a(n) = 2^(n-1) +1 = A000051(n-1) for n>0. - M. F. Hasler, Sep 22 2013