|
%I #38 Mar 01 2023 13:52:52
%S 13,21,33,53,85,137,221,357,577,933,1509,2441,3949,6389,10337,16725,
%T 27061,43785,70845,114629,185473,300101,485573,785673,1271245,2056917,
%U 3328161,5385077,8713237,14098313,22811549,36909861,59721409,96631269
%N Number of binary strings of length n with no substrings equal to 0001, 1000 or 1001.
%H R. H. Hardin, <a href="/A164485/b164485.txt">Table of n, a(n) for n = 4..500</a>
%H Martin Griffiths, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Griffiths/gr48.html">On a Matrix Arising from a Family of Iterated Self-Compositions</a>, Journal of Integer Sequences, 18 (2015), #15.11.8.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1).
%F G.f.: -x^4*(-13 + 5*x + 9*x^2) / ((x - 1)*(x^2 + x - 1)). - _R. J. Mathar_, Jan 19 2011
%F a(n) = 4*Fibonacci(n) + 1. - _Bruno Berselli_, Jul 26 2017
%F From _Colin Barker_, Jul 26 2017: (Start)
%F a(n) = 1 - (4*(((1 - sqrt(5))/2)^n - ((1 + sqrt(5))/2)^n))/sqrt(5) for n>3.
%F a(n) = 2*a(n-1) - a(n-3) for n>6.
%F (End)
%o (PARI) Vec(-x^4*(-13 + 5*x + 9*x^2) / ((x - 1)*(x^2 + x - 1)) + O(x^60)) \\ _Colin Barker_, Jul 26 2017
%o (Python)
%o from sympy import fibonacci
%o def a(n): return 4*fibonacci(n) + 1
%o print([a(n) for n in range(4, 101)]) # _Indranil Ghosh_, Jul 26 2017
%K nonn,easy
%O 4,1
%A _R. H. Hardin_, Aug 14 2009
|
