A166578 a(n) = a(n-3) + 2^(n-4) with a(1) = 1, a(2) = 2, a(3) = 1.

1, 2, 1, 2, 4, 5, 10, 20, 37, 74, 148, 293, 586, 1172, 2341, 4682, 9364, 18725, 37450, 74900, 149797, 299594, 599188, 1198373, 2396746, 4793492, 9586981, 19173962, 38347924, 76695845, 153391690, 306783380, 613566757, 1227133514, 2454267028

Offset: 0

Author

Paul Curtz, Oct 17 2009

Keywords

• nonn
• easy

Comments

a(n) and successive differences: 1,1,2,1,2,4,5,10,20,37; 0,1,-1,1,2,1,5,10,17,37; 1,-2,2,1,-1,4,5,7,20,37; -3,4,-1,-2,5,1,2,13,17,34; 7,-5,-1,7,-4,1,11,4,17,43; -12,4,8,-11,5,10,-7,13,26,25; Rows must be taken by pairs (companions because a(n)-a(n-3) alternatively gives A131577 and A011782 also companions). Note a(3n+2)=2*a(3n+1)=4*a(3n), n positive; see A113405. Sum of consecutive three terms of even rows gives 0,4,32,256.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (2,0,1,-2).

Programs

Mathematica

RecurrenceTable[{a[1]==1,a[2]==2,a[3]==1,a[n]==a[n-3]+2^(n-4)},a[n],{n,40}] (* or *) LinearRecurrence[{2,0,1,-2},{1,2,1,2},40] (* Harvey P. Dale, Sep 14 2011 *)

PARI

Vec((1-3*x^2-x^3)/(1-2*x-x^3+2*x^4)+O(x^99)) \\ Charles R Greathouse IV, Jan 25 2012

Formula

For n > 4, a(n) = 2a(n-1) + a(n-3) - 2a(n-4).

a(3n) = (8^n - 8)/14 + 1, a(3n-1) = (8^n - 8)/28 + 2, a(3n-2) = (8^n - 8)/56 + 1.

G.f.: (1-3*x^2-x^3)/(1-2*x-x^3+2*x^4). - Colin Barker, Jan 25 2012

Extensions

Edited by Charles R Greathouse IV, Nov 04 2009