login
Number of binary strings of length n whose only palindromic prefixes are "1" and "11".
0

%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