OFFSET
0,4
COMMENTS
This sequence gives the number of binary strings of length n that begin with an odd-length palindrome (not including the trivial palindrome of length one).
'1011' is an example of a string that begins with an odd-length palindrome: the palindrome '101', which is of length 3.
'1101' is an example of a string that does not begin with an odd-length palindrome. (It does begin with the even-length palindrome '11'.)
The probability of a random infinite binary string beginning with an odd-length palindrome is given by: limit n -> infinity a(n)/(2^n), which is approximately 0.7322131597821109.
LINKS
Peter Kagey, Table of n, a(n) for n = 0..1000
FORMULA
EXAMPLE
For n = 4 the a(3) = 8 solutions are: 0000 0001 0100 0101 1010 1011 1110 1111.
PROG
(Ruby)
s = [0, 0]
(2..N).each { |n| s << 2 * s[-1] + (n.even? ? 0 : 2**(n/2+1) - s[n/2+1]) }
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Peter Kagey, Jan 25 2015
STATUS
approved