How do i prove these type of questions? I am Really stuck.

Question

How do I solve this textbook question:

If we let $n\geq 1$ be an integer and define $A_n$ to be the number of bitstrings of length $n$ that do not contain $101$

1. How do I determine $A_1$, $A_2$, $A_3$ $A_4$

and how do I prove that for each integer $n\geq4$,

$A_n$ = 3 +$A_1$+$A_2$+$A_3$+$\cdot$$\cdot$$\cdot$+$A_{n-4}$+$A_{n-3}$+$A_{n-1}$ = 3+$\sum_{k=1}^{n-3}{A_k} {+} A_{n-1}$

Answer 1

haha I'm working on the same question, what I currently have is, consider....

i) a bit string of length n that begins with a zero and doesn't contain 101, removing the first character then there are $A_{n-1}$

ii) now a bit string that begins with 10 and doesn't contain a 101, thus the third character has to be a 0, so now we can remove the first 3 charaters and we have $A_{n-3}$ ways of doing this one

iii)now a bit string beginning with 11 that doesn't contain 101, we have to break this up into 2 cases, the proceeding character is a a) 0, b) 1

a) if the third character is a 0 then by definition the fourth must be a 0, and there are $A_{n-4}$ ways of doing this

b)if the third character is another 1 we go back to the start of iii and consider the proceeding cases we will end up with the conclusion without a loss of generality that $An = A_1+A_2+A_3+⋅⋅⋅+A_{n−4}+A_{n−3}+A_{n−1}$

but now I'm confused as to where this magic 3 comes into play maybe you can help there

Answer 2

Part 1 is just by counting. You use all possible cases $2^n$ minus number of cases where $101$ is included, the answer is $2,4,7,12$.

Part 2. We consider a bitstring of length $n$ that do not contain $101$.

If the string starts with $0$ (We are considering the $n$th bit), remove this bit, we get a bitstring of length $n-1$ that do not contain $101$. There are totally $A_{n-1}$ such string.

If the string starts with $10$ (We are considering the $n-1$th digit), the $n-2$th bit must be $0$, remove the first $3$ bits, we get a bitstring of length $n-3$ that do not contain $101$. There are totally $A_{n-3}$ such string.

If the string starts with $110$ (We are considering the $n-2$th digit), the $n-3$th bit must be $0$, remove the first $4$ bits, we get a bitstring of length $n-4$ that do not contain $101$. There are totally $A_{n-4}$ such string.

Inductively, if the string starts with $11\dots 1$ (We are considering the $3$th digit), the $2$th bit must be $0$, remove the first $n-2$ bits, we get a bitstring of length $1$ that do not contain $101$. There are totally $A_{1}$ such string.

Now the remaining case is a string composing $n-2$ of $1$, and two free bits. To make the string without $101$, we can choose the last two bits as $00,11,10$, here comes the $3$.

Hence the total possible cases are sum of all these choices, which gives you the formula.