Problem
COM-B1-M10-P015 No Three Zeros
#15
★★★☆☆ Level 3 of 5
How many binary strings of length \(10\) contain no three consecutive zeros?
Use final blocks \(1\), \(01\), \(001\).
Let \(a_n\) be the number of strings of length \(n\). A valid string ends in \(1\), \(01\), or \(001\), according to its final block of zeros. Therefore \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\). Initial values are \(a_0=1\), \(a_1=2\), \(a_2=4\). Then \(a_3=7\), \(a_4=13\), \(a_5=24\), \(a_6=44\), \(a_7=81\), \(a_8=149\), \(a_9=274\), \(a_{10}=504\).
Three-term recurrence via final block.