# Recurrence relation for the number of bit strings that contain the string $01$

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

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