Chapter 9.3, Problem 27ES

For each integer $n\ge 0$ . let $a_k$be the number of bit strings of length n that do not contain the pattern 101.

a. Show that $a_k=a_{k-1}+a_{k-3}+a_{l-4}+\cdots +a_0+2$ , for every integer $k\ge 3$ .
b. Use the result of part (a) to show that if $k\ge 3$ , then $a_k=2a_{k-1}+a_{k-2}+a_{k-3}$ .