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 &gt; 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.
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 &amp; n=4
\\000&amp;0000
\\001&amp;0001
\\010(X)&amp;0010(X)
\\011&amp;0011
\\100&amp;0100(X)
\\101&amp;0101(X)
\\110&amp;0110
\\111&amp;0111
\\&amp;1000
\\&amp;1001
\\&amp;1010(X)
\\&amp;1011
\\&amp;1100
\\&amp;1101
\\&amp;1110
\\&amp;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).
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 &amp; n=4
\\000&amp;0000
\\001&amp;0001
\\010(X)&amp;0010(X)
\\011&amp;0011
\\100&amp;0100(X)
\\101&amp;0101(X)
\\110&amp;0110
\\111&amp;0111
\\&amp;1000
\\&amp;1001
\\&amp;1010(X)
\\&amp;1011
\\&amp;1100
\\&amp;1101
\\&amp;1110
\\&amp;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).