Prove that for all integers $n > 3$, $y_{n+1} = 2 x_n$ Let $x_n$ be the number of 0/1 strings of length $n$, not including the sequence 010. Let $y_n$ be the number of 0/1 strings of length $n$, not including 0011 or 1100. Prove that for all integers $n > 3$, $y_{n+1} = 2x_n$.
I don't know where to start with this one, especially with the exclusion of certain sequences.
Any help getting me on the right track would be appreciated. Thanks.
 A: EDIT:It is difficult to write this formally, so I'm just going to give you a hint:
For $n\geq 4$, you can write $0/1$ strings of length $n$ in $2^n$ ways. To calculate $x_n$, we should calculate how many of those strings include $010$. You can show by induction that this number is number is $2^{n-1}-n$, so $x_n=2^n-(2^{n-1}-n)=2^{n-1}+n$ (alternatively, you can show this formula for $x_n$ by induction. Also, if you write all sequences of length $n$ for $n=3,4,5$ in a matrix, for example, in the lexicographical order, and then mark the sequences containing $010$, you get a nice pattern, which may help you understand where did this number come from:$$\begin{bmatrix}n=3 & n=4
\\000&0000
\\001&0001
\\010(X)&0010(X)
\\011&0011
\\100&0100(X)
\\101&0101(X)
\\110&0110
\\111&0111
\\&1000
\\&1001
\\&1010(X)
\\&1011
\\&1100
\\&1101
\\&1110
\\&1111
\end{bmatrix}$$
for $n=5$ the marks make something like $(X)-(X)(X)-(X)(X)(X)(X)-(X)-(X)(X)-(X)$, and so on).
Assuming the result of the exercise, we should have $y_n=2x_{n-1}=2^{n-1}+2n-2$, which you can also showto be valid by induction (making a similar table may help you again).
