Finding the number of bit sequences without using recursion 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.
 A: 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$.
A: 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
