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,3

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

Links

Table of n, a(n) for n=2..37.

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)

Example

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.

Sequence in context: A000047 A101172 A192677 * A006544 A110536 A049861

Adjacent sequences: A307906 A307907 A307908 * A307910 A307911 A307912

Keyword

nonn,easy

Author

Lewis Chen, May 04 2019

Status

approved