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}$$ 
 A: 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);

A: 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<n$. 
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}$. 
A: 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).
