Recurrence Relation for a binary string
an is the number of strings of length n in which every 0 is immediately followed by at least two consecutive 1's. Example: the string 101111 is allowed, but 01110 is not.
so what the problem asks for is to find a recurrence relation and initial conditions for an. now i had something going where:
if it starts with a 011, that would be an-3
starts with a 1, it could be 1011_________ = an-4, or 11011_____ = an-5, .....etc (where ____ could be 0 or 1)
i was just wondering if this is the right approach? and how to also figure in the possibility of another zero appearing somewhere along the string of _____.