A recurrence relation for the number of n-digit binary sequences without the “101”

combinatorics

Find a recurrence relation for $a_n$, which is the number of n-digit binary sequences without the sub-sequence "101". I know that $a_1=2$, $a_2=4$, $a_3=7$, $a_4=12$, but what is the general relation?
Thanks!

Best Answer

The binary sequences of length $n$ can only be formed by

  • Preceding a length $n-1$ sequence with a $0$
  • Preceding a length $n-2$ sequence with $10$ or $11$ such that the second digit matches the third digit of the new sequence. E.g. $000\mapsto \boxed{10}000$ and $100\mapsto \boxed{11}100$.
  • Preceding a length $n-4$ sequence with $1100$

Hence we have the recurrence $$a_n=a_{n-1}+a_{n-2}+a_{n-4}$$ which gives $$a_n=2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897,\dots$$

Related Question