I'll post the full solution when I find time.

Might as well post the solution then, though SamE's hint does rather give it away...

I did it by induction.

From a sequence $(x_1,x_2,...,x_n)$ construct another sequence $(y_0,y_1,...,y_n)$ of length $n+1$ such that $y_0=0$ and $y_i=\sum_{k=1}^{i}{x_k} \pmod{2}$ .It is easy to see that such a constuction is bijective.Also the sequence of the first type has a subsequence $(0,1,0) \Leftrightarrow$ the sequence of the second type has a subsquence $(0,0,1,1)$ or $(1,1,0,0)$.The case when $y_1=1$ can be seen analogously by interchanging the $0$'s ans $1$'s.We are through.....

The less intelligent but quite straightforward recursion solution: Let $c_n$ denote the number of strings counted by $a_n$ that end with $01$, and let $d_n$ denote the number of strings counted by $b_n$ that end with either $001$ or $110$. Verify for small $n$ that $b_{n+1} = 2a_n$ and $d_{n+1} = 2c_n$. We now establish recursions for $a_n, b_n, c_n, d_n$. To count $a_n$, we have $a_{n-1}$ choices for the first $n-1$ bits and $2$ ways to append an $n$th bit, but we cannot append a $0$ to the $c_{n-1}$ strings ending with $01$. So, we have \[a_n = 2a_{n-1} - c_{n-1}.\]Count $b_n$ similarly. For each string counted by $d_{n-1}$, there is one way to illegally append $0$ or $1$, so we have \[b_n = 2b_{n-1} - d_{n-1}.\]To count $c_n$, we have $a_{n-2}$ choices for the first $n-2$ bits and must append $01$ to each of them, but those $(n-2)$-length strings ending with $01$ fail. So, we have \[c_n = a_{n-2} - c_{n-2}.\]Count $d_n$ similarly. We have $d_{n-2}$ choices for the first $n-2$ bits, and the last bit of the $(n-2)$-length string determines the necessary $(n-1)$th and $n$th bits we must append. However, this fails when the $(n-2)$-length string ends in either $001$ or $110$ since we are forced to append $10$ and $01$, respectively, which is illegal. So, we have \[d_n = b_{n-2} - d_{n-2}.\]Now apply induction using these recursions to finish.

The set of $3$ consecutive terms for a sequence $a_n$ are $000, 100, 101, 110, 111, 001, 011.$ The set of $4$ consecutive terms for a sequence $b_n$ are $0000, 0001, 0010, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1101, 1110, 1111.$ In the sequence $b_{n+1},$ there are $n-2$ strings of $4$ consecutive terms. In a sequence $a_n,$ there are $n-2$ string of $3$ consecutive terms. Then, for each starting $3$ string in sequence $a_n$, can append 2 different starting number (0 or 1) to the start to make a valid string of $b_{n+1}$. This process can be reversed. Therefore, we have formed a 1 to 2 bijection between $b_{n+1}$ to $a_n$, so $b_{n+1} = 2a_n$ for all $n$.

Consider the map from sequences of the latter form to sequences of the first form by \[ (y_1, \dots, y_{n+1}) \mapsto (y_1 + y_2, y_2 + y_3, \dots, y_n + y_{n+1}). \]It is $2$-to-$1$. The end.

Williamgolly wrote: The set of $3$ consecutive terms for a sequence $a_n$ are $000, 100, 101, 110, 111, 001, 011.$ The set of $4$ consecutive terms for a sequence $b_n$ are $0000, 0001, 0010, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1101, 1110, 1111.$ In the sequence $b_{n+1},$ there are $n-2$ strings of $4$ consecutive terms. In a sequence $a_n,$ there are $n-2$ string of $3$ consecutive terms. Then, for each starting $3$ string in sequence $a_n$, can append 2 different starting number (0 or 1) to the start to make a valid string of $b_{n+1}$. This process can be reversed. Therefore, we have formed a 1 to 2 bijection between $b_{n+1}$ to $a_n$, so $b_{n+1} = 2a_n$ for all $n$. What if, say, the starting string of one of the terms in $a_n$ is $011$. Then we can't append 0 at the start to make a valid term for $b_n$. How is the bijection valid? Is there anything that I'm missing here?

$a_n$ is the sequence of absolute differences of $b_{n+1}$, where we can pick the first term to be either $1$ or $0$. Thus $b_{n+1} = 2a_n$.

SamE wrote:

I'll post the full solution when I find time. legend says he still cannot find time

@above I think I know why @SamE is still not being able to find time. This quote explains the reason. Some great person once said - ``$\textbf{If you cannot prove a statement using induction,}$ $\textbf{try inducting on the inductive step of that induction and if that still doesn't work,}$ $\textbf{try inducting on the inductive step of the inductive step of the induction and so on....}$". AIME style recursion vibes . We proceed using induction. Base case clearly works. Note that you can perform a map by switching the $0$s with $1$s and vice versa. Note that this map is an involution and thus a bijection. So we can just consider $\dfrac{b_n}{2}$ and then we would only have to handle the condition where no $0$, $0$, $1$, $1$ sequence is there. Then we have to prove that $b_{n+1}=a_n$. $x_n$ denote the number of $n$ lengthed sequence which end with a $0$, $1$ and satisfy the condition for $a_n$. This gives $a_n=2a_{n-1}-x_{n-1}$. Similarly, $y_n$ denote the number of $n$ lengthed sequences which end with $0$, $0$, $1$ and satisfy the condition for $b_n$. This gives $b_n=2b_{n-1} -y_{n-1}$. Thus it suffices to prove that $x_{n-1}=y_{n}$. A bit of case checking gives $x_n=a_{n-2}-x_{n-2}$ and $y_n=y_{n-3}$. Now we do even more induct lol. $x_{n-1}=y_{n}\iff a_{n-3}-x_{n-3}=y_{n-3}\iff a_{n-3}=x_{n-3}+x_{n-4}$ where the last equality follows due to induction. It just leaves us to prove $a_n=x_n+x_{n-1}$. Andddd, guess what? Even more induct! YAYY! We now have $a_n=x_n+x_{n-1}\iff 2a_{n-1}-x_{n-1}=x_n+x_{n-1}\iff x_n=2x_{n-2}$ where the last equality again follows due to induction. This simply follows from that the digit after $x_n$ cannot be $0$ and must be $1$ due to the condition of $a_n$ and then there are $2$ choices for the last digit and we are done.

We can define a binary sequence of length $n$ using $a$, $b$ where $a$ and $b$ determine whether the next digit in the sequence is different from the previous or the same respectively, and we can choose a beginning value $0$ or $1$. For example $1abaa = 10010$. Then the number of $n+1$ length sequences using $a, b$ that does not contain the string $bab$ is the same as the number of $n+1$ sequences avoiding $0011$ and $1100$ given a starting value of $1$ or $0$. So then it follows that $b_{n+1} = 2a_{n}$ as desired.