Let's say $A_n$ is the number of binary string that has length $n$ and does not contain the substring 101. Calculate $A_n$ for $n=1,2\cdots8.$ Find a recurrence relation for $A_n$. What does the solution of that recurrence look like?
These are the solutions that I have found for calculations for $A_n$. $1, 4, 7, 12, 20, 32, 48, 96$.
I've calculated this by hand. But how I do find the recurrence? I see that 4, 7, 12, 30 are Fibonacci – 1, but not after or before that.
But I'm not sure how to do this or if this is even correct.
Best Answer
We get a relationship between valid strings of length $n$ with those of length $n+1$ as follows:
If a word counted by $a^{[\emptyset]}_n$ is appended by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.
If a word counted by $a^{[1]}_n$ is appended by $0$ from the left it contributes to $a^{[01]}_{n+1}$. If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.
If a word counted by $a^{[01]}_n$ is appended by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. Appending from the left by $1$ is not allowed since then we have an invalid string starting with $101$.
We can now derive a recurrence relation from (1) - (4):
Hint: We have $a_5=\color{blue}{21}$ valid strings of length $5$. The $2^5-21=11$ invalid strings are \begin{align*} \color{blue}{101}00\qquad0\color{blue}{101}0\qquad00\color{blue}{101}\\ \color{blue}{101}01\qquad0\color{blue}{101}1\qquad01\color{blue}{101}\\ \color{blue}{101}10\qquad1\color{blue}{101}0\qquad\color{lightgrey}{10101}\\ \color{blue}{101}11\qquad1\color{blue}{101}1\qquad11\color{blue}{101} \end{align*}