<s>[INST] 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}$$ 
 [/INST] 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).
</s>