|
Say n is 8. How would I ever solve this problem? I've Googled around and searched this site but I haven't come up with much. I'm not even looking for the answer necessarily, just the process by which I'd go about getting it. I started by calculating the total number of bit strings of length 8 as $2^8$. From there where should I go? |
|||
|
|
You can define $A(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in $1$, $B(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in one $0$, , $C(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in two $0$'s, and $D(n)$ as the number of strings of length $n$ containing three zeros. Then $A(1)=1$, $B(1)=1$, $C(1)=0$, $D(1)=0$ and for $n>1$, $$ \begin{align} A(n)&=A(n-1)+B(n-1)+C(n-1) \\ B(n)&=A(n-1)\\ C(n)&=B(n-1)\\ D(n)&=2D(n-1)+C(n-1) \end{align} $$ |
|||||||||||||||||
|
