$\begin{align*} &\text{Lets us assume, } \\ \\ &A(n) = \text{Number of strings ends with 1 and has 01 substring} \\ &B(n) = \text{Number of strings ends with 0 and has 01 substring} \\ &\text{and let us call the strings satisfying the property as valid strings.} \\ \\ & \text{We can see that } B(n) = F(n-1) \quad \text{ For } B(n) \text{, We can not get more number of strings} \\ \\ &A(n) = \left [\text{All strings of length }(n - 2) \right ].01 \quad + \\ &\quad \left [\text{All the valid strings of length }(n - 1) \text{ that ends with 1} \right ].1 \\ \\ &A(n) = 2^{n-2} + A(n-1) \\ &A(n) = 2^{n-2} + 2^{n-3} + A(n-2) \\ & ....... \\ &A(n) = 2^{n-2} + 2^{n-3} + .... + 2^{n - (n-1+1)} + A(n - (n-1)) \\ &A(n) = 2^{n-1} - 1 \\ \\ &\Rightarrow F(n) = 2^{n-1} - 1 + F(n-1) \\ \\ &\text{Initial condition, } F(1) = 0 \quad \text{ because valid strings are of atleast length 2} \\ \end{align*}$
