%I #7 Jul 29 2019 13:17:30
%S 1,1,2,3,5,8,15,27,52,99,195,382,757,1499,2986,5945,11865,23678,47309,
%T 94519,188942,377689,755191,1510000,3019625,6038493,12076244,24150989,
%U 48300491,96597996,193193033,386380121,772754322,1545496779,3090981745,6181939812
%N Number of binary strings of length n whose only palindromic prefixes are "1" and "11".
%C Obviously, any 1-length prefix will be palindromic. Without the 2-length prefix condition, there is only one such string for every length: 10, 100, 1000, etc. (A000012).
%F a(2) = 1, a(3) = 1, a(2*k) = 2*a(2*k-1)-a(k+1)+a(k), a(2*k+1) = 2*a(2*k)-a(k+1)
%e a(5) = 3 because there are three such strings: 11000, 11001, and 11010. For example, 11100 is not such a string, because a prefix (111) is palindromic.
%Y Cf. A000012, A006995.
%K nonn,easy
%O 2,3
%A _Lewis Chen_, May 04 2019