So I got this problem: compute the number of n bit string that do not contain pattern 010 that have no leading 0, one leading zero, two leading zero, and so on.
So far, I got the expression:
Sn = Sn-1 + Sn-3 + Sn-4...+ S1
However the solution is:
Sn = Sn-1 + Sn-3 + Sn-4...+ S1 + 3
My question is, where + 3 come from? thx
update: I was thinking that if the string that does not contain 010 begin w/ 1, the rest will be Sn-1. if the string begin with one 0 (which mean the first two bit is 01), the next bit have to be 0 -> Sn-3 and so on