0

I've looked up this question in here and found one whose answer didnt look complete to me or maybe I couldnt figure it out correctly.. I can understand the first part of the answer $a_n = a_{n-1} + a_{n-3} + a_{n-4} + a_{n-5} + \cdots + a_{1} + 3$ But my problem mosly is on last part $a_1 + 3$ Any help like "explanation for dummies" kind of answer would be great ! What is the best approach to analyze these kinda problems .. The related link: $n$-Bit Strings Not Containing $010$ Thanks a lot !

Community
  • 1
bhd
  • 71
  • Can you link to the other question? This formula doesn't look right. Aside from the two $a_{n-3}$ terms (which I figure is a typo) the formula says $a_2=a_1+3$. But there are two good strings of length $1$ and $4$ of length $2$ so this is not the right answer. – lulu Dec 09 '15 at 21:08
  • @lulu im sorry for being careless, for the answer ,I edited the question with the link added .. – bhd Dec 09 '15 at 21:12
  • The explanation to that question seems thorough. The "$+3$" arises because prepending strings of the form $0^k11$ does not get you any of the three strings $0^n,0^{n-1}1,0^{n-2}11$. Note that the explanation specifically says this recursion only holds for $n≥3$, excluding the counterexample I pointed out earlier. Note, this is not how I would have thought about the problem...are you trying to understand how to construct these strings recursively or are you trying to understand this particular recursion? – lulu Dec 09 '15 at 21:25
  • On a tangential note, I think $a_{n}=2a_{n-1}-a_{n-2}+a_{n-3}$ also works. First term counts how to add $0$ or $1$, second term takes out strings that end with $10$, third term adds back strings ending with $110$, so only those ending with $010$ are removed. – Kevin Long Dec 09 '15 at 21:39
  • @lulu thanks for the tips , I have only a half understanding of forming recurrences like these, specially as soon as I think I know already how to find a correct recursive solution for these kind of problem , I suddenly encounter new one with s strange form(to me). And I conclude that I have omitted some aspects of the recurrence! Its still vague and unclear to me, trying to find it out . Thank u so much – bhd Dec 09 '15 at 22:21
  • @kevin long Thanks for the reply kevin, im trying to figure out your approach, it makes more sense to me.. im grateful – bhd Dec 09 '15 at 22:33

1 Answers1

1

I think understanding the $+ 3$ revolves around understanding the first bits so bare with me as I explain my interpretation. First, keep in mind that if we have a "good" string (one that meets the given requirements) of length $n-1$ and append a $1$ to the start, we will always get a "good" string of length $n$, since adding a $1$ to the front can't create an occurrence of $010$. This contributes the $S_{n-1}$ term.

However, the string needn't necessarily begin with $1$. It could start with some string of $0$'s. Now, we assume two things: the first is that the string of $0$'s is followed by $11$ and secondly, that the $11$ is followed by a good string. This is because we know that if $1$ follows a $0$ in the string, then to make it a good string, that $1$ must be followed by another $1$. Then, we'll have something of the form $000...011$+[good string]. Then since $010$ occurs in neither of the concatenated strings, nor in the part where they meet, then the result is a good string. Thus, we begin with $011$+[good string of length $n-3$] contributing $S_{n-3}$, $0011$+[good string of length $n-3$] contributing $S_{n-4}$, and so on until we get to a string of $n-3$ $0$'s, $11$ and then $0$ or $1$, which is counted by $S_{1}=2$.

Now we consider the exceptions: as I said before, we assume, among other things, that there is something following the $11$ buffer. However, we could have $00...011$, which is a good string. We also might not even have the $11$ buffer: we can also have $00...01$ and $00...0$. In these cases, the complete buffer is not necessary. However, in any other case where we have a string of $0$'s followed by $1$ followed by at least $2$ entries, then we refer to the previous cases.

Kevin Long
  • 5,159