# Recurrence Relation - # of binary strings with given property

Let $$a_n$$ be the number of binary strings of length $$n$$ with the property that each entry is adjacent to at least one entry of the same type.

ex: $$11000111$$ is a valid string but $$11011000$$ is not valid

$$\textbf{(a) Find a_1,a_2,a_3,a_4,a_5,a_6,a_7}$$

If someone can check that my attempt is correct, I would really appreciate it.

$$a_1=0$$ since we cannot have just $$0$$ or just $$1$$ as there will be no adjacent of the same type

$$a_2=2$$: either $$00$$ or $$11$$

$$a_3=2$$: either $$000$$ or $$111$$

$$a_4=4$$:

Reasoning:

$$\textbf{If we start with a 0}$$: For the second entry we have $$1$$ choice as we are forced to put a $$0$$ since we started with a $$0$$. For the third entry we have $$2$$ choices, and similarly for the fourth entry we have $$1$$ choice. So there are $$2$$ such strings.

$$\textbf{If we start with a 1}$$: For the second entry we are forced to put a $$1$$. For the third entry we have $$2$$ choices, and for the fourth entry we have $$1$$ choice. So there are $$2$$ such strings.

So $$a_4=2+2=4$$ strings.

Following the same method for the remaining:

$$a_5=4$$

$$a_6=8$$

$$a_7=8$$

$$\textbf{(b) Find the recurrence relation for a_n}$$

$$a_n= \begin{cases} 2a_{n-2}&n \text{ even},\\ a_{n-1}&n \text{ odd} \end{cases}$$

• Something is wrong in your solution. Consider $n = 5$ - the possible strings are 11111, 00000, 11000, 00111, 11100, 00011, and $a_5 = 6$. Nov 13, 2018 at 17:48
• Shouldn't $a_6$ be 10 and $a_7$ be 14? Nov 14, 2018 at 2:01

Using $$z$$ for ones and $$w$$ for zeros we get the generating function

$$F(z, w) = (1+z^2+z^3+\cdots) \times \sum_{q\ge 0} (w^2+w^3+\cdots)^q (z^2+z^3+\cdots)^q \\ \times (1+w^2+w^3+\cdots).$$

This is

$$\left(1+\frac{z^2}{1-z}\right) \times \sum_{q\ge 0} \frac{w^{2q} z^{2q}}{(1-w)^q (1-z)^q} \\ \times \left(1+\frac{w^2}{1-w}\right).$$

Continuing without the distinction between ones and zeros we get

$$\left(1+\frac{z^2}{1-z}\right)^2 \sum_{q\ge 0} \frac{z^{4q}}{(1-z)^{2q}} \\ = \left(1+\frac{z^2}{1-z}\right)^2 \frac{1}{1-z^4/(1-z)^2} \\ = (1-z+z^2)^2 \frac{1}{(1-z)^2-z^4}.$$

The difference of two squares yields $$(1-z+z^2)^2 \frac{1}{(1-z+z^2)(1-z-z^2)}.$$

which simplifies to

$$\bbox[5px,border:2px solid #00A000]{ G(z) = \frac{1-z+z^2}{1-z-z^2}.}$$

From the coefficients of this OGF we get the sequence

$$1, 0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, \\ 1220, 1974, 3194, 5168, 8362, \ldots$$

which is OEIS A006355 where these data are confirmed. Now for the coefficients we have

$$[z^0] G(z) (1-z-z^2) = G_0 = [z^0] (1-z+z^2) = 1$$

and hence $$G_0 = 1.$$ Furthermore

$$[z^1] G(z) (1-z-z^2) = G_1-G_0 = [z^1] (1-z+z^2) = -1$$

so $$G_1 = 0.$$ Next we find

$$[z^2] G(z) (1-z-z^2) = G_2-G_1-G_0 = [z^2] (1-z+z^2) = 1$$

so $$G_2 = 2.$$ For $$n\ge 3$$ we get

$$[z^n] G(z) (1-z-z^2) = G_n - G_{n-1} - G_{n-2} = [z^n] (1-z+z^2) = 0$$

so that for $$n\ge 3$$

$$\bbox[5px,border:2px solid #00A000]{ G_n = G_{n-1} + G_{n-2}.}$$

The following Maple code documents the problem definition that was used.

ENUM :=
proc(n)
option remember;
local ind, d, res, pos;

if n=0 then return 1 fi;
if n=1 then return 0 fi;
if n=2 then return 2 fi;

res := 0;

for ind from 2^n to 2*2^n-1 do
d := convert(ind, base, 2)[1..n];

if d[1] = d[2] and d[n] = d[n-1] then
for pos from 2 to n-1 do
if d[pos-1] <> d[pos] and
d[pos] <> d[pos+1] then
break;
fi;
od;

if pos = n then
res := res + 1;
fi;
fi;
end;

res;
end;

X := n-> coeftayl((1-z+z^2)/(1-z-z^2), z=0, n);


Your argument seems wrong to me. In particular the following part.

If we start with a $$0$$: For the second entry we have one choice as we are forced to put a $$0$$ since we started with a $$0$$. For the third entry we have two choices, and similarly for the fourth entry we have one choice.

That last sentence seems to be true for $$n=4$$, but not in general for $$n>4$$. In this case it is only true if you choose $$1$$ for the third entry, but if you've chosen $$0$$ then you have two choices.

That analogous happens in the case where you start with $$1$$.

For the recurrence relation I think the following should work. For any $$m$$ let $$b_m$$ and $$c_m$$ denote respectively the strings of the desired form that start with a $$0$$ and with a $$1$$ repectively. Note that $$b_m=c_m=a_m/2$$. So this is all a bit silly, but let's do it for the sake of keeping the argument clear.

Let's fix $$n\geq 3$$. I'll calculate $$b_n$$ in terms on $$c_m$$ for $$m.

How many strings are there that have $$0< s < n$$ zeroes in a row before having a one? As you've noted if $$s=1$$ then the answer is zero strings. For $$s\geq 2$$ then observe that the answer is $$c_{n-s}$$.

Using this show that $$b_m=1+ \Sigma_{2\leq s < n} c_{n-s}$$.

You can take this as a sequence of stretches of at least two equal symbols. In ordinary generating function terms a sequence of two or more would be represented by:

\begin{align*} z^2 + z^3 + \dotsb &= \frac{z^2}{1 - z} \end{align*}

A sequence of the above in turn would be:

\begin{align*} 1 + \frac{z^2}{1 - z} + \left(\frac{z^2}{1 - z}\right)^2 + \dotsb &= \frac{1}{1 - \frac{z^2}{1 - z}} \\ &= \frac{1 - z}{1 - z - z^2} \end{align*}

Consider the Fibonacci sequence, defined by $$F_{n + 2} = F_{n + 1} + F_n$$ with $$F_0 = 0, F_1 = 1$$. It's generating function is:

\begin{align*} F(z) &= \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2} \end{align*}

But also:

\begin{align*} \sum_{n \ge 0} F_{n + 1} z^n &= \frac{F(z) - F_0}{z} = \frac{1}{1 - z - z^2} \end{align*}

We see that our generating function is:

\begin{align*} \frac{1 - z}{1 - z - z^2} &= \sum_{n \ge 0} (F_{n + 1} - F_n) z^n \\ &= \sum_{n \ge 0} F_{n - 1} z^n \end{align*}

So the number of sequences of length $$n$$ is $$F_{n - 1}$$, where we extend to $$F_{-1} = 1$$ (as it should be to get one sequence of length 0).