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 !!

  • $\begingroup$ Isn't that just all $2^n$ bit strings minus the $n+1$ strings $1\ldots 10\ldots 0$? $\endgroup$ – Hagen von Eitzen Oct 4 '16 at 12:45
  • $\begingroup$ I don't understand case $1$. The string $101$ starts with $1$ yet it contains $01$. $\endgroup$ – lulu Oct 4 '16 at 12:47
  • $\begingroup$ @lulu i meant that only .that if it start with $1$ then go and check $01$ in $a_{n-1}$ $\endgroup$ – virat Oct 4 '16 at 12:49
  • $\begingroup$ @HagenvonEitzen i am not getting you ! $\endgroup$ – virat Oct 4 '16 at 12:53
  • 2
    $\begingroup$ 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. $\endgroup$ – lulu Oct 4 '16 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.