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