%I #27 Nov 26 2025 15:59:39

%S 0,4,6,12,20,36,58,100,160,268,430,708,1140,1860,3002,4876,7880,12772,

%T 20654,33444,54100,87564,141666,229252,370920,600196,971118,1571340,

%U 2542460,4113828,6656290,10770148,17426440,28196620,45623062,73819716,119442780,193262532

%N a(n) = if n mod 2 = 0 then 8*F(n)-n otherwise 8*F(n)-4, where F() = Fibonacci numbers A000045.

%C Number of self-avoiding walks on the strip {0,1} X Z.

%C Variant of A038577. [_R. J. Mathar_, Dec 13 2008]

%H A. T. Benjamin, <a href="https://www.fq.math.ca/Papers1/44-4/quartbenjamin04_2006.pdf">Self-avoiding walks and Fibonacci numbers</a>, Fib. Quart., 44 (No. 4, 2006), 330-334.

%H Doron Zeilberger, <a href="https://arxiv.org/abs/math/9506214">Self Avoiding Walks, The Language of Science, and Fibonacci Numbers</a>, arXiv:math/9506214 [math.CO], Jun 03 1995.

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,-2,-3,1,1).

%F G.f.: -2*x*(2*x^4-x^3-3*x^2+x+2) / ((x-1)^2*(x+1)^2*(x^2+x-1)). - _Colin Barker_, Mar 18 2013

%t LinearRecurrence[{1, 3, -2, -3, 1, 1}, {0, 4, 6, 12, 20, 36}, 40] (* _Jean-François Alcover_, Jan 09 2019 *)

%t Table[If[EvenQ[n],8Fibonacci[n]-n,8Fibonacci[n]-4],{n,0,40}] (* _Harvey P. Dale_, Jun 12 2019 *)

%o (PARI) a(n) = if (n % 2, 8*fibonacci(n)-4, 8*fibonacci(n)-n); \\ _Michel Marcus_, Sep 07 2015

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_, Sep 30 2007