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

1, 1, 2, 3, 5, 8, 15, 27, 52, 99, 195, 382, 757, 1499, 2986, 5945, 11865, 23678, 47309, 94519, 188942, 377689, 755191, 1510000, 3019625, 6038493, 12076244, 24150989, 48300491, 96597996, 193193033, 386380121, 772754322, 1545496779, 3090981745, 6181939812

Offset: 2

Author

Lewis Chen, May 04 2019

Keywords

• nonn
• easy

Comments

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).

Examples

			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.
		

Crossrefs

Cf. A000012, A006995.

Formula

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)