First find the first three.
Note that no string in can end in a zero.
If you add a 1 to the right end of any string in you have a valid string in .
What is the complete list for ?
That is a way to proceed.
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 _____.
alright so what i figured out for an is the following:
an = an-1 + (0.5 * an-1) + an-2 + (0.5* an-2) + ...a2 + (0.5 * a2) + a1.
where each (0.5 * an__) is rounded up. This is because to get lets say a5, you can add 1 to the end of every string in a4, and add also add 1 to the start of the string in a4 that starts with a 10.
so a4 = {0111,1111,1011}, and a5 = {01111,11111,10111,11011}
"Actually it should be ."
I don't think that is correct.
if a(5)=4, a(3)=2
a(6) = a(5) + a(3) = 6
but:
a(6): {111111,101111,110111,111011,011111} = 5
Isn't it something like:
a(n) = a(n-1) +1 with initial conditions a(0)=a(1)=a(2)=1
where n >=3. I am not sure if this is a valid way of stating a recurrence relation though...