# Find a recurrence relation for $a_n$, the number of binary strings of length $n$, which have 3 consecutive 1's.

As the title states, I am tasked with finding finding a recurrence relation according to the specific constraints. I have a start to the problem, but I'm really having trouble identifying the pattern for the recurrence relation. My first step was to go through the first few cases to see if a pattern emerged. Here is what I found:

Here's where I got a bit stuck. I am currently trying to look for patterns in terms of taking the previous terms and adding a combination of 1's and 0's to them. I found the terms for length 5 by taking the previous term (length 4) and adding a 1 to the front of all the terms, then adding a 0 to the front of all the terms, then a 1 to the back, then a 0 to the back. I ended up with a few duplicates that I then had to remove. Any help towards the next steps I need to take or hints would be greatly appreciated!

• You should have $a_5=8$. You seem to have double counted 01110 – Henry May 3 at 22:05

Hint:

If you let

• $$a_n$$ be the number of the number of binary strings of length $$n$$ which have $$3$$ consecutive $$1$$s

• $$b_n$$ be the number of the number of binary strings of length $$n$$ which do not have $$3$$ consecutive $$1$$s but which end with exactly two $$1$$s

• $$c_n$$ be the number of the number of binary strings of length $$n$$ which do not have $$3$$ consecutive $$1$$s but which end with exactly one $$1$$

• $$d_n$$ be the number of the number of binary strings of length $$n$$ which do not have $$3$$ consecutive $$1$$s but which end with exactly zero $$1$$s

and consider adding a $$1$$ or $$0$$ to the end of shorter strings, then you can say $$a_{n}=2a_{n-1}+b_{n-1} \\ b_{n}=c_{n-1} \\ c_{n}=d_{n-1} \\ d_{n}=d_{n-1}+c_{n-1}+b_{n-1}$$

which you can then turn into $$a_{n}=2a_{n-1}+d_{n-3} \\ d_{n}=d_{n-1}+d_{n-2}+d_{n-3}$$ and if you are brave then into something like $$a_{n}=3a_{n-1}-a_{n-2}-a_{n-3}-2a_{n-4}$$

You know the starting conditions up to $$a_4$$, so could find a generating function solution if not a simple closed form. Incidentally, $$d_n$$ seems to be related to the so-called Tribonacci numbers