A118870 - OEIS

%I #21 Sep 08 2022 08:45:25

%S 1,2,4,8,15,28,53,100,188,354,667,1256,2365,4454,8388,15796,29747,

%T 56020,105497,198672,374140,704582,1326871,2498768,4705689,8861770,

%U 16688516,31427872,59185079,111457548,209897245,395279228,744391228,1401840170

%N Number of binary sequences of length n with no subsequence 0101.

%C Column 0 of A118869 and column 10 of A209972.

%H G. C. Greubel, <a href="/A118870/b118870.txt">Table of n, a(n) for n = 0..1000</a>

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

%F G.f.: (1 +x^2)/(1 -2*x +x^2 -2*x^3 +x^4).

%F a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n>=4.

%F a(n) = A112575(n-1) + A112575(n+1). - _R. J. Mathar_, Dec 10 2011

%e a(5) = 28 because among the 32 (=2^5) binary sequences of length 5 only 01010, 01011, 00101 and 10101 contain the subsequence 0101.

%p a[0]:=1:a[1]:=2:a[2]:=4:a[3]:=8: for n from 4 to 35 do a[n]:=2*a[n-1]-a[n-2]+2*a[n-3]-a[n-4] od: seq(a[n], n=0..35);

%t CoefficientList[Series[(1+x^2)/(1-2x+x^2-2x^3+x^4),{x,0,40}],x] (* _Geoffrey Critzer_, Nov 28 2013 *)

%o (Magma) [n le 4 select 2^(n-1) else 2*Self(n-1) -Self(n-2) +2*Self(n-3) -Self(n-4): n in [1..41]]; // _G. C. Greubel_, Jan 14 2022

%o (Sage)

%o @CachedFunction

%o def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))

%o def A118870(n): return A112575(n-1) + A112575(n+1)

%o [A118870(n) for n in (0..40)] # _G. C. Greubel_, Jan 14 2022

%Y Cf. A000071, A000073, A005251, A112575, A118869, A209972, A332052.

%K nonn

%O 0,2

%A _Emeric Deutsch_, May 03 2006