0

Find the recurrence relation for the number of bit strings that contain the string $01$

I know it is answered here

But i have a doubt.I mean i just want to check my approach,where it is wrong!!

For Finding recurence relation containing $01$,$a_{n}$ Lets us start with String starting with $1$,

case 1: If it starts with $1$ $\Rightarrow$ ,it may contain $01$ in $a_{n-1}$

Starting with $11$ is covered in case 1

case 2:Starting With $01$ check in other $2^{n-2}$ sets

Thus can't we write $a_{n}=a_{n-1}+2^{n-2}$ ??? Where i am wrong please correct me !!

Community
  • 1
sourav_anand
  • 551
  • Isn't that just all $2^n$ bit strings minus the $n+1$ strings $1\ldots 10\ldots 0$? – Hagen von Eitzen Oct 04 '16 at 12:45
  • I don't understand case $1$. The string $101$ starts with $1$ yet it contains $01$. – lulu Oct 04 '16 at 12:47
  • @lulu i meant that only .that if it start with $1$ then go and check $01$ in $a_{n-1}$ – sourav_anand Oct 04 '16 at 12:49
  • @HagenvonEitzen i am not getting you ! – sourav_anand Oct 04 '16 at 12:53
  • Still not following. You say "if it starts with $1\implies$ No chance it will contain $01$." Maybe you meant something entirely different, but how are we to guess? – lulu Oct 04 '16 at 12:54
  • @lulu i had made mistake in expressing ..i meant that if it starts with $1$ then we have to check $01$ in $a_{n-1}$ ! i will update my question! – sourav_anand Oct 04 '16 at 12:56
  • I don't know what "check in" means. This is all very vague. Let's do small $n$. $a_1=0$, yes? There are no strings of length $1$ that contain $01$. So then you tell me that $a_2=0+1=1$ which is true! Good. Now $a_3$. You tell me $a_3=a_2+2=1+2=3$. But we have $011,010,001,101$. So, we have a problem. Go through your argument carefully and see where it breaks down for $n=3$. – lulu Oct 04 '16 at 13:07
  • 2
    But, honestly, the problem is trivial. Look at strings that do not contain $01$. That means that, whenever a $0$ occurs all subsequent characters must also be $0$. Thus we only have $1^a0^b$. Easy to count those. – lulu Oct 04 '16 at 13:14
  • @lulu,i think $a_{n-1}+2^{n-2}$ is creating problem because whenever we are seeing a $1$,we are switching to $a_{n-1}$,while it may contain $0$ before it which will count to $01$thus it is not counting as per expectation – sourav_anand Oct 05 '16 at 10:57
  • Well. One obvious problem with your method is that you appear to be assuming that every good string either begins with $1$ or $01$, which is obviously false. For $a_3$ this causes you to omit $001$. But, really, go over the easy way to do it (outlined in my prior comment). – lulu Oct 05 '16 at 11:17
  • @lulu you are right ! i did not use $0$ as a "starting good string" because there will no be scope of counting it if the next string is $1$ and hence my equation fails ..thankx for pointing it out! – sourav_anand Oct 05 '16 at 11:21

0 Answers0