# Recurrence Relation for a binary string

• March 24th 2010, 12:01 PM
Math101
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 _____.
• March 24th 2010, 01:12 PM
Plato
First find the first three.
$A_1:\{1\},~~a_1=1$
$A_2:\{11\},~~a_2=1$
$A_3:\{011,111\},~~a_3=2$
Note that no string in $A_n$ can end in a zero.
If you add a 1 to the right end of any string in $A_3$ you have a valid string in $A_4$.
What is the complete list for $A_4$?
That is a way to proceed.
• March 24th 2010, 02:00 PM
Math101
alright so A4 = {1011,0111,1111} = 3, A5 = {10111,01111,11111,11011}...etc

but how would i write this as a recurrance relation for an = ?
• March 24th 2010, 02:13 PM
Plato
Quote:

Originally Posted by Math101
alright so A4 = {1011,0111,1111} = 3, A5 = {10111,01111,11111,11011}...etc
but how would i write this as a recurrance relation for an = ?

Well that is for you to work on.
Here are more hints.
Any valid string must the last three $\cdots 011\text{ or }\cdots 111$.
It is safe to add a 1 to any string in $A_{n-1}$.
BUT that does not get all in $A_n$.
What else does? Be careful do not get repeats.
• March 25th 2010, 10:36 AM
Math101
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}
• March 25th 2010, 11:34 AM
Plato
Quote:

Originally Posted by Math101
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.

Actually it should be $a_n=a_{n-1}+a_{n-3}$.
We add 1 to the end of every string in $A_{n-1}$ and add 011 to the end each string in $A_{n-3}$.
You should try that to see why it works with the $A_n$’s we already have.
• March 25th 2010, 03:32 PM
jones357
"Actually it should be http://www.mathhelpforum.com/math-he...d70bd2fd-1.gif."

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...
• March 25th 2010, 03:44 PM
Plato
Quote:

Originally Posted by jones357
a(6) = a(5) + a(3) = 6
but: a(6): {111111,101111,110111,111011,011111} = 5

But you missed one in $A_6=\{111111,101111,110111,111011,011111,{\color{b lue}011011}\}$
• March 25th 2010, 03:49 PM
jones357
I had misunderstood the original question to mean that after a 0, there must be all 1's of which there must be at least 2.
• March 25th 2010, 03:55 PM
Plato
Quote:

Originally Posted by jones357
there must be all 1's of which there must be at least 2.

"every 0 is immediately followed by at least two consecutive 1's." does not mean that.