%I #34 Jan 27 2015 01:14:14
%S 0,0,2,4,10,20,44,88,182,364,740,1480,2980,5960,11960,23920,47914,
%T 95828,191804,383608,767500,1535000,3070568,6141136,12283388,24566776,
%U 49135784,98271568,196547560,393095120,786199088,1572398176,3144813974
%N Number of binary words of length n that are not "bifix-free".
%C Also the number of binary strings of length n that begin with an even length palindrome. (E.g., f(4) = 10 with strings 0000 0001 0010 0011 0110 1001 1100 1101 1110 1111.) - _Peter Kagey_, Jan 11 2015
%C The probability that a random, infinite binary string begins with an even-length palindrome is: lim n -> infinity a(n)/2^n ~ 0.7322131597821108... . - _Peter Kagey_, Jan 26 2015
%H Peter Kagey, <a href="/A094536/b094536.txt">Table of n, a(n) for n = 0..1000</a>
%F a(n) = 2^n - A003000(n).
%F Let b(0)=1; b(n) = 2*b(n-1) - 1/2*(1+(-1)^n)*b([n/2]); a(n) = 2^n - b(n). - _Farideh Firoozbakht_, Jun 10 2004
%F a(0) = 0; a(1) = 0; a(2*n+1) = 2*a(2*n); a(2*n) = 2*a(2*n-1) + 2^n - a(n). - _Peter Kagey_, Jan 11 2015
%F G.f. g(x) satisfies (1-2*x)*g(x) = 2*x^2/(1-2*x^2) - g(x^2). - _Robert Israel_, Jan 12 2015
%p a[0]:= 0:
%p for n from 1 to 100 do
%p if n::odd then a[n]:= 2*a[n-1]
%p else a[n]:= 2*a[n-1] + 2^(n/2) - a[n/2]
%p fi
%p od:
%p seq(a[i],i=0..100); # _Robert Israel_, Jan 12 2015
%t b[0]=1;b[n_]:=b[n]=2*b[n-1]-(1+(-1)^n)/2*b[Floor[n/2]]; a[n_]:=2^n-b[n];Table[a[n], {n, 0, 34}]
%o (Ruby)
%o s = [0,0]
%o (2..N).each { |n| s << 2 * s[-1] + (n.odd? ? 0 : 2**(n/2) - s[n/2]) }
%Y See A003000 for much more information.
%Y Cf. A094537.
%Y A254128(n) gives the number of binary strings of length n that begin with an odd-length palindrome.
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_, Jun 06 2004
%E More terms from _Farideh Firoozbakht_, Jun 10 2004
%E Corrected by Don Rogers (donrogers42(AT)aol.com), Feb 15 2005