Finding the number of bit sequences without using recursion

Question

How many 8-bit strings without three consecutive 1's are there that start with 1?

I used recursion and found that the answer is 68, but this was asked in a high school test so I am looking for an answer that doesn't use recursion.

Answer 1

You can just use brute force (implicitly inclusion-exclusion):

There are $2^8=256$ strings with $8$ bits but half start with $0$ leaving $2^7=128$ starting with $1$ like $1.......$ and then

• drop $2^{4}=16$ like $1....111$ ;
• drop $2^{3}=8$ like $1...1110$ ;
• drop $2^{3}=8$ like $1..1110.$ ;
• drop $2^{3}=8$ like $1.1110..$ ;
• drop $2^{3}-1=7$ like $11110...$, but not $11110111$ which was already dropped ;
• drop $2^{4}-3=13$ like $1110....$, but not $11101111$ or $11101110$ or $11100111$ which were already dropped ;

leaving $128-16-8-8-8-7-13 =68$ remaining possibilities

Answer 2

Let states $\{0,1,2\}$ represent the number of consecutive ones in the current run. The adjacency matrix is $$ A= \begin{pmatrix} 1 &1 &0\\ 1 &0 &1\\ 1 &0 &0 \end{pmatrix}. $$ The numbers of walks of length 7 are recorded by $$ A^7= \begin{pmatrix} 44 & 24 & 13\\ 37 & 20 & 11\\ 24 & 13 & 7 \end{pmatrix}. $$

The initial state is 1, so the desired path count is the sum of the entries in the second row, namely $37+20+11=68$.