Let $B(n)$ be the number of bit strings that contain “$01$” derive a recurrence relation for $B(n)$ and solve iteratively

Question

I believe I have found the recurrence relation to be $$B\left(n\right)=B\left(n-1\right)+2^{n-1}-1$$ with Initial Condition $B(0)=0$ (I am a bit unsure about the initial condition though but I think it is correct)

Now I am trying to solve $B(n)$ using iteration, this is what I have so far: $$B\left(n\right)=B\left(n-1\right)+2^{n-1}-1$$ $$B\left(n\right)=B\left(n-2\right)+2^{n-2}+2^{n-1}-\left(2\right)1$$ $$B\left(n\right)=B\left(n-3\right)+2^{n-3}+2^{n-2}+2^{n-1}-\left(3\right)1$$ $$=B\left(n-k\right)+2^{n-k}+2^{n-\left(k-1\right)}+2^{n-\left(k-2\right)}-\left(k\right)1$$ and then I let n=k since the intial condition is $B(0)$ but this is where I get confused I am not sure what to do from here? $$=B\left(0\right)+2^0+2^1+2^2+...+2^{\left(?\right)}-n$$

Answer 1

You’re on the right track:

$$\begin{align*} B(n)&=B(n-1)+2^{n-1}-1\\ &=B(n-2)+2^{n-2}+2^{n-1}-2\\ &=B(n-3)+2^{n-3}+2^{n-2}+2^{n-1}-3\\ &\;\;\vdots\\ &=B(n-k)-k+\sum_{i=1}^k2^{n-i}\\ &\;\;\vdots\\ &=B(0)-n+\sum_{i=1}^n2^{n-i}\\ &=-n+\sum_{i=0}^{n-1}2^i\\ &=-n+2^n-1\\ &=2^n-n-1\,. \end{align*}$$

Answer 2

Yes, $B_0=B_1=0$. Let $A_n = 2^n - B_n$ be the number of bit strings that do not contain $01$, so $A_0=1$. For $n>1$, condition on whether the first bit is $0$ or $1$ to obtain recurrence relation $$A_n = 1 + A_{n-1},$$ which implies that $$A_n = n+1.\tag1$$ Hence $$B_n = 2^n - A_n = 2^n - (1 + A_{n-1}) = 2^n - 1 - (2^{n-1} - B_{n-1}) = 2^{n-1} - 1 + B_{n-1},$$ or just use $(1)$ to conclude that $B_n = 2^n - n - 1$.